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?

  • Where did you get 1000(n-1) ? Look again. – kevin cline Sep 30 '15 at 0:16
  • Should it be 1000-(n-1)? – ohbrobig Sep 30 '15 at 0:30
  • Oops meant 1000-(n+1) – ohbrobig Sep 30 '15 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 '15 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 '15 at 17:52
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.

|improve this answer|||||
-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....

|improve this answer|||||
  • If you are going to downvote, maybe you should explain what you believe is wrong.... – ohbrobig Oct 1 '15 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 '15 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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