0

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

3
  • 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
    Commented Feb 28, 2021 at 11:13
  • 1
    Does this answer your question? What is O(...) and how do I calculate it?
    – gnat
    Commented 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
    Commented Feb 28, 2021 at 15:38

2 Answers 2

3

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.