CODEWITHSUNDEEP
algorithmtime-complexitynested-loops
geekybedouin
geekybedouin

Reputation: 559

Nested Loops Time Analysis

Ok I am taking an Algorithm Class and am studying for the Exam... Unfortunately.. I can't understand the concept behind the nested loops time analysis

there are three loops in this code 

for (i=1->n)
 for (j=1->i)
   for (k=1->i)
     x=x+1;

I can't understand how to figure out the answer :s Any Answer would be a great help Thanks Folks :)

Upvotes: 1

Views: 5077

Answers (2)

Yochai Timmer
Yochai Timmer

Reputation: 49251

You need to sum up the loops, it's a just multiple sigmas that need to be calculated:

Sigma Calculation

The 1 in the inner sigma is the complexity of what you're doing inside the innermost loop.

Upvotes: 3

jitendra
jitendra

Reputation: 1458

When i=1, k-loop runs 1 time and j-loop runs 1 time. Total=1.1=1 time
When i=2, k-loop runs 2 times and j-loop runs 2 times. Total=2.2=4 times
When i=3, k-loop runs 3 times and j-loop runs 3 times. Total=3.3=9 times
When i=n, k-loop runs n times and j-loop runs n times. Total=n.n=n^2 times

So, time complexity of algorithm is O(1+2^2+3^2+...n^2)=O(n(n+1)(2n+1)/6) =O(n^3)

Upvotes: 1

Related Questions