running time complexity of Algorithms

[saqib_604]

Hi! I want to know, how to calculate running time complexity of a given code or algorithm. some one please help me. code is given below.

x = 0;

for (a=1;a<=n;a=a*9)
{ 
  for (b=1; b<=3n; b++)
   {
     for(c=0;c<n; c=c+5)
       {
          x++;
       }
   }
}

I think,
there is for the outer loop, the inner statements run log3n and the inner most loop will run n/5 times. but I am confused. about the b loop. and due to this I cannot understand, how to do it.

[apines]

There was a similar question here. Try to review the example, and if you still encounter any trouble I'll go over it with you.

[saqib_604]

And what about outer for loop where a = a*9 ?

[saqib_604]

There was a similar question here. Try to review the example, and if you still encounter any trouble I'll go over it with you.

And what about outer for loop where a = a*9 ?

[apines]

You want to know after how many iterations a will go from 1 to n when jumping in steps of a*9. After the first iteration a=9, after the second iteration a=9*9=9^2=81, third iteration a=9*9*9=9^3. After k iterations, you will have a=9^k, Assuming the a = n after x iterations, it means that n=9^x -> x = log9(n).

[saqib_604]

You want to know after how many iterations a will go from 1 to n when jumping in steps of a*9. After the first iteration a=9, after the second iteration a=9*9=9^2=81, third iteration a=9*9*9=9^3. After k iterations, you will have a=9^k, Assuming the a = n after x iterations, it means that n=9^x -> x = log9(n).

will there be O(1) for x=0 and x++?

[saqib_604]

then after finding time of remaining loops, I have to add them?

[saqib_604]

Ok! Thanks for this favour.

[apines]

You need to multiply. For each iteration of the outer loop, the middle loop is doing all of it's iterations. For each iteration of the middle loop, the inner loop is doing all of it's iterations. Let's take an easier example:

for(int i = 0; i < 3; ++i)
{
   System.out.println("Started Outer Loop!");
   for(int j = 0; j < 5; ++j)
   {
      System.out.println("Started Inner Loop!");
   }
   System.out.println("Finished Outer Loop!")
}

Now, when the outer loop enters the first iteration, and starting to execute the lines inside its code block, the first thing that will happen then, is that the line "Started Outer Loop!" will be printed. Afterwards the inner loop will start. When entering the second loop, from j=0 to j=4, meaning 5 iterations, the line "Started Inner Loop!" will be printed. Afterwards the line "Finished Outer Loop!" will be printed. After that the first iteration of the outer loop will be finished, and we will start it again, this time with i=1. This procedure will go over and over again until i=3, and the outer loop finishes. This means that for 3 times, from i=0 to i=3, the inner loop did 5 iterations, from j=0 to j=5 - overall 3*5=15. On the screen, at the end, you will have the total number of 3 "Started Outer Loop!", 3 "Finished Outer Loop!" and 15 "Started Inner Loop!" (obviously not in that order :))

[saqib_604]

oh! thanks, you saved me.

[apines]

No problem :) please mark the thread as solved.