CODEWITHSUNDEEP
c++algorithmloopstimecomplexity-theory
mjl007
mjl007

Reputation: 775

Time Complexity on triple Nested For loops where indexes are dependent on each other

I have this c++ like pseudo code here:

 for ( i = 1; i ≤ (n – 2); i++)
     for (j = i + 1; j ≤ (n – 1); j ++)
         for (k = j + 1; k ≤ n; k++)
             Print “Hello World”;

I am fairly certain the time complexity of this particular block of code is O(n^3) because it is triple nested for loop and they are all going to at minimum n - 2 so I generalized (n-2) * (n-1) * n

But I have been trying to solve the actual time complexity function. This is how far I got and could not proceed any further:

summation from i = 1 to n-2, summation from j = (i+1) to n-1, summation from k = (j+1) to n.

I understand that the inner most loop performs n - (j+1) steps, the middle loop performs (n-1)-(i+1) steps, and the outer loop performs (n-2)-i steps. I just need some pointers on how to simplify the summations to come to a time complexity function.

Thank you!

Upvotes: 1

Views: 1148

Answers (2)

rcgldr
rcgldr

Reputation: 28828

If interested, the loops iterate through every combination of n things taken 3 at a time, starting with (1,2,3), (1,2,4), ... , and ending with (n-2,n-1,n), which is n! / (( 3! )( (n-3)!) ) = (n)(n-1)(n-2)/6 = (n^3 - 3n^2 + 2n) / 6 , which leads to O(n^3).

Upvotes: 2

Cauterized
Cauterized

Reputation: 41

Don't run the loop from 1 to less or equal a value. Your code is equal to:

for ( i = 0; i < (n – 2); i++)
  for (j = i; j < (n – 1); j ++)
    for (k = j; k < n; k++)
      Print “Hello World”;

So your inner loop runs n-j, the middle one multiplies it with n-1-i and the outer one multiplies it with n-2. So you get (n-j)*(n-1-i)*(n-2). n has O(n) complexity. Because of i runs from 0 to (n-1), you could replace it with O(n) (because sum(0, n) = 0 + 1 + .. + N = 0.5 * n^2 = O(n^2)). It is the same with j. So you get (O(n)-O(n))*(O(n)-1-O(n))*(O(n)-2) = O(n)*(n)*O(n) = O(n^3).

For details why you could replace i with O(n) see "Nested loops" at this.

Upvotes: 1

Related Questions