Expected time complexity of O(n^2), but it results in O(n). Can some explain why?

user_13118631 0
Viewed 156

What should be the time complexity of the following code? I tried to think and come up with O(n2) but the output says it to be of O(n). Can someone please explain through code?

for(int i = 0; i < n; i++){
    for(; i < n; i++){
        cout << i << endl;
    }
}
time-complexity algorithm c++
3 Answers

The complexity of your code is O(n).

Why?

Because, even though you have written two for loops, which probably made you thinking the complexity is O(n2), your code is actually one for loop like:

for (i = 0; i < n; i++){
    std::cout << i << std::endl;
}

Once the inner for loop finishes, i is equal to n and therefore the condition of outer for loop i < n is no longer satisfied.

user_55173780

One point to be noted while using such for loops is that your using a single variable.

Irrespective of how many outer loops you add, your code will result in the same with the condition i<n prevailing in all. The innermost loop is the one which will run till i=n-1, the rest of which simply won't satisfy the condition.

for(int i=0; i<n; i++)
{ for(; i<n; i++)
  { for(; i<n; i++)
    { for(; i<n; i++) // and so on.
       std::cout<<i<<"\n";
    }
  }
}

Providing a variant to this, if you were to observe one such case of O(n2) complexity, your condition would have been i<n*n:

for(int i=0; i<n; i++)
{ for(; i<n*n; i++)
    std::cout<<i<<"\n";
}
Admin1

Time complexity of your code is O(n) and not O(n^2) because when inner loop ends, at that time value of i has already reached to n . So outer loop cannot run any more.

for(int i = 0; i < 2; i++){
    for(; i < 2; i++){
        cout << i << endl;
    }
   //after loop run two times i has value 2.
   //and outer loop cannot run anymore
}
user_132194900
Related