3

I understand how to get a general picture of the big O of a nested loop, but what would be the operations for each loop in a nested for loop?

If we have:

for(int i=0; i<n; i++)
{
    for(int j=i+1; j<1000; j++)
    {
        do something of constant time;
    }
}

How exactly would we get T(N)? The outer for loop would be n operations, the inner would be 1000(n-1) and the inside would just be c is that right?

So T(n)=cn(1000(n-1)) is that right?

6
  • Where did you get 1000(n-1) ? Look again. Sep 30, 2015 at 0:16
  • Should it be 1000-(n-1)?
    – ohbrobig
    Sep 30, 2015 at 0:30
  • Oops meant 1000-(n+1)
    – ohbrobig
    Sep 30, 2015 at 1:59
  • This will always remain O(n) since this algorithm will always scale linear. There is no logarithmic increase or decrease to be found. Obviously with higher N's this will take longer, but it will be a linear scaling always.
    – hoppa
    Sep 30, 2015 at 8:24
  • I'll just leave this here. (If you click "more terms" enough times, you will see the maximum, after which this is no longer accurate)
    – Ordous
    Sep 30, 2015 at 17:52

2 Answers 2

3

The limit as n approaches infinity reveals big O(n). The internal loop only executes for the first 999 n. For n > 999 the internal loop does not run and the instructions become constant.

How to write this all as a function T(n)? Of that I am not certain.

-1

It is O(1), not linear, because the inner loop will only be executed when n is less than 1000, so for big n (ex: 1,001 and 100,000,000) it will be the same. Like you said, it might be linear till 1000, but it is constant after that....

2
  • If you are going to downvote, maybe you should explain what you believe is wrong....
    – ohbrobig
    Oct 1, 2015 at 6:36
  • You're talking about the complexity of the inner loop exclusively. It's not clear without closely looking at your original question that what you really want to know is the complexity of each loop separately. On top of that, we may have to assume you want to know the overall complexity after examining the loops together.
    – ThisClark
    Oct 1, 2015 at 19:13

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.