Search code examples
algorithmtime-complexitynested-loops

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 :)

Solution

  • 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)