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.
-
What have you tried so far? What do you think it is? Please demonstrate a basic effort to have solved the problem before posting it here.templatetypedef– templatetypedef2014-04-02 19:48:53 +00:00Commented Apr 2, 2014 at 19:48
-
Try to determine the number of iterations of the first loop, and for each iteration of the first loop, the number of iterations of the second one, and so on... Also, the overall complexity will depend on the complexity of the body of the third loop, but you can leave that for the end. You can try drawing a tree, it may be easier for you.manash– manash2014-04-02 20:07:50 +00:00Commented Apr 2, 2014 at 20:07
Add a comment
|
2 Answers
A formal solution to determine the order of growth of your algorithm:
answered Apr 11, 2014 at 14:33
Mohamed Ennahdi El Idrissi
2,9872 gold badges21 silver badges35 bronze badges
Comments
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.
