Big O Nested For Loop Breakdown
https://softwareengineering.stackexchange.com/questions/298592
-
10-10-2020 - |
Question
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?
La solution
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.
Autres conseils
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....