CODEWITHSUNDEEP
big-otime-complexity
srock
srock

Reputation: 413

Time complexity of 2 for loops with a O(n) operation

I have 2 for loops with an operation which would take o(n) inside 1 of the nested for loops.

for (i=0;i<someLength;i++){
  for(j=i+1;j<someLength;j++){
      //some operation requiring O(n)
     }
}

What will be the overall complexity?

Upvotes: 1

Views: 305

Answers (3)

srock
srock

Reputation: 413

As mentioned by @Mohamed above in mathematical terms, the complexity for the code in question is O(n^3).

Quick explanation(worst case i.e. looping through the entire loop):

Outer FOR loop complexity = O(n)

Inner FOR loop complexity = O(n)

Total complexity so far = O(n^2)

Now, in my question I had mentioned there was an operation inside the inner FOR loop which had a complexity of O(n) --> which is almost the same as 1 more FOR loop inside the Inner FOR loop, that makes the total complexity O(n^3).

Upvotes: 0

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

You can formally represent your loops using Sigma notation, then expand it:

enter image description here

Upvotes: 1

ctzdev
ctzdev

Reputation: 676

The Big-Oh of two nested for loops is O(n^2), assuming that "someLength" is very large.

Explanation:

for(int i = 0; i < 100; i++)
{
     cout << "i: " << i << " ";
}

The above code executes in .02 seconds according to the compiler on my system (using <ctime> library).

In this case n is equal to 100. So 100/.02 = 5000.

for(int i = 0; i < 100; i++)
{
    for(int j = i + 1; j < 100; j++)
    {
        cout << "i: " << i << " " << endl << "j: " << j << " ";
    }
}

The above equates to ~1.9 seconds. Now using the fact that the Big-Oh of two nested for loops is O(n^2).

Since n is equal to 100, we have 100^2 or 10000. So using the result of 5000 from the above calculation, we get 10000/5000 = 2 seconds.

1.9 seconds is close enough to 2 seconds, therefore the run-time of your block of code is indeed O(n^2).

Upvotes: 0

Related Questions