CODEWITHSUNDEEP
big-o
ant2009
ant2009

Reputation: 22606

Big O notation with nested for loops and single for loop

    int a = 0, b = 0;    
    for (i = 0; i < N; i++) {
        for (j = 0; j < N; j++) {
            a = a + j;
        }
    }

    for (k = 0; k < N; k++) {
        b = b + k;
    }

I am trying to work out the time complexity of the above.

I was thinking it was O(n^2 + n) my reasoning is:

n^2 : nested for loops
n   : Adding the single loop

However, the confirmed answer is O(n^2)

My questions is why is the last for loop included as that on its own would be O(n)

Many thanks for any suggestions,

Upvotes: 1

Views: 1481

Answers (4)

Nikhil Misal
Nikhil Misal

Reputation: 93

The first set of nested loops is O(N^2) and the second loop is O(N). This is O(max(N^2,N)) which is O(N^2).

As quoted from : http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html >> TEST YOURSELF #3

Upvotes: 1

lyst
lyst

Reputation: 381

You don't need to mention the O(n) because it's peanuts compared to the O(n^2) classification. Its the same idea as when your algorithm has an O(n) part and an O(1) part - you don't call it O(n+1), you call it O(n).

This article has a good explanation: https://www.interviewcake.com/article/java/big-o-notation-time-and-space-complexity

Upvotes: 2

mc01
mc01

Reputation: 3780

With Big-O notation you take the highest-order component and drop other multiplication factors. The reason is that as "n" gets larger in an exponential process, adding another "n" doesn't really change it much.

If n=1000000 then n^2 is 1000000000000. Saying + n to make it 10000001000000 doesn't have a significant impact. As n grows larger, the impact is even more negligible.

The inverse is true for something like n log n where you're increasing by an order of magnitude, so keeping that multiplication factor has an appreciable impact.

Upvotes: 2

templatetypedef
templatetypedef

Reputation: 373082

You are technically correct that the runtime is O(n^2 + n) because the initial loop is quadratic and the second is linear. However, the convention with big-O notation is to drop constant factors and lower order terms from big-O expression, since big-O notation talks about long term Limiting behavior. As a result, the given answer of O(n^2) is a better way of accounting for the runtime. Your answer isn't technically incorrect, but it's not considered good mathematical style.

Upvotes: 1

Related Questions