Algorithm Complexity loop

Question

Time complexity of a triple-nested loop

for(int i=0; i<n; i++)
    for(int j=i+1; j<n; j++)
        for(int k=j+1; k<n; k++)

I want to know the right solution of time complexity.

Answer 1

A formal solution to determine the order of growth of your algorithm:

Answer 2

First guess: three loops depending on n, so it should be O(n³)

If you try to compute the exact complexity you have to compute it for the inner an multiply it with the outer loop.

inner loop takes O(n-k)
middle loop takes O(n-j + n-j-1 + ... + n-j-n) = O((n-j) ⋅ (n-j+1) / 2) = O((n-j)²)
outer loop takes O((n-1)² + (n-2)² + ... + (n-n+1)²) = O(n³)

Sure this is not exact, but in terms of big-O it is exact enought.