Small confusion about time complexity

Question

Suppose we have a code:

for(int i=0;i<n;i++) sum+=i;

We say the time function here is: f(n) = n+1+n = 2n+1. The order of the time function is 1. So, our time complexity becomes O(n). But, for the following code:

for(int i=0;i<n;i++)
{
    for(int j=0;j<n;j*=2)
    {
         statement;
    }
}

For this code our time function f(n) = n + n log(n) + n log(n) = 2n log(n) +n. But here also the order of the time function is 1. So, why we say the time complexity of this function O(nlogn) instead of O(n)?

Answer 1

Big-O notation is about identifying the term that grows the fastest.

It doesn't matter if the constant out the front is huge, or tiny. Its a constant and does not change how quickly a term grows.

eg: 1/123456789 * N^3 + 123456789 * N^2 + 300000000000000000000 * N

In the smaller values of N the linear term is dominant. But it is quickly over taken by the N^2 term, and that term itself is overtaken by the N^3.

As N gets large the behaviour of the function always tends toward the quickest growing term. this is why the example is gave is O(N^3) even though for small values of N it behaves more quadratically on linearly. In your example its why its O(nlogn).

Answer 2

Read your example carefully. The loop for j doesn’t iterate log n times. It iterates zero times if n <= 0 and runs forever if n > 0.

Once you figured out where you went wrong, you should be able to figure out the log n as well.