# Small confusion about time complexity

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)`?

• Why do you say that `fn(n) = n + 2 n log(n)` would have order 1? Clearly, O(n log n) is not in a subset of O(n).
– amon
Feb 28, 2021 at 11:13
• Does this answer your question? What is O(...) and how do I calculate it?
– gnat
Feb 28, 2021 at 14:19
• Where did you get "`f(n) = n+1+n = 2n+1`" from? You're correct that we'd generally describe that first loop as O(n), though there's something off about the reasoning.
– Nat
Feb 28, 2021 at 15:38

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).

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.