CODEWITHSUNDEEP
javaalgorithmcomplexity-theory
Mustehssun Iqbal
Mustehssun Iqbal

Reputation: 566

Time complexity for a triple for loop

What have I done before

Asymptotic analysis of three nested for loops

I was solving the time complexity of this algorithm. seeing that the outer loop runs n times and inner loop 1 runs i times, I applied the summation and got the two outer loops' complexity to be n(n plus 1)/2. Then the inner loop executes j times equals to summation of j from j is 0 to j is n(n plus 1)/2. This yields the total complexity of O(n4).

The problem

Asymptotic analysis of three nested for loops

Seems like my answer is wrong. Where did I made the mistake?

Upvotes: 1

Views: 2128

Answers (1)

ajb
ajb

Reputation: 31699

You counted the wrong thing. The inner loop executes j times, and j is always less than n. Therefore, for each of your n(n-1)/2 times the inner loop starts, the body of the inner loop will be executed less than n times, which means the total number of times the loop executes is at most n(n-1)/2 * O(n), which is at most O(n^3). What I think you did was double-counting. You tried to use the "summation" of j, which is the total number of times the for (int j... loop executes. But that information is already contained in the computation you already made, n(n-1)/2; using that information again and multiplying it with n(n-1)/2 is double-counting.

Upvotes: 2

Related Questions