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

Vote count:

0

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!

asked 41 secs ago

Moses J Lee

1

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