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

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 '21 at 11:13
Does this answer your question? [What is O(...) and how do I calculate it?](https://softwareengineering.stackexchange.com/questions/132331/what-is-o-and-how-do-i-calculate-it) — gnat, Feb 28 '21 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 '21 at 15:38

score 3 · Accepted Answer · answered Feb 28 '21 at 10:49

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

score 0 · Answer 2 · answered Feb 28 '21 at 13:49

0

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.

answered Feb 28 '21 at 13:49

gnasher729

42,090
4
59
119

Small confusion about time complexity

2 Answers2