Algorithm Step Counts

[amatech]

Hi guys, can anyone help me determine the step counts of the following instructions in terms of n?

for i = 1 to 2 * n
j = i + 1
while j >= 1
j = j – 1

Thank you!

[apines]

Assuming that the code is

for i = 1 to 2 * n 
{
   j = i + 1
   while j >= 1
   {
      j = j – 1   
   }
}

Then let's analyze the complexity: The outer loop is simple, it goes from 1 to 2n, meaning 2n iterations. The inner loop is dynamic. The first iteration of the outer loop, when i = 1, then j=1+1=2 and it goes until j is no longer bigger or equals to 1, with decremation of 1 in each of the inner loop's iteration - meaning it will go twice: first iteration j=2, second iteraion j=1, and then j=0 and the inner loop exists. The second iteration of the outer loop i=2, meaning j=3, meaning that following the same logic as before we will have 3 iterations. The next iteration of the outer loop i=3, j=4 and we will have 4 iterations. This will go on until i=2n, j=2n+1, and then we will have 2n+1 iterations. So the inner loop will go 1+2+3+...+2n+(2n+1) iterations. Using the sum of arithmetic progression we can tell that this equals to ((2n+2)(2n+1))/2. So the inner loop goes 2n iterations, the outer loop goes ((2n+2)(2n+1))/2 iterations, making the total number of iterations to be 2n*((2n+2)(2n+1))/2=n*((2n+2)(2n+1)).

[amatech]

Thanks apines, very good explanation. this helped alot!

Best regards!

[apines]

Glad I could help you :) Please mark the thread as solved.

[amatech]

Glad I could help you :) Please mark the thread as solved.

Hi apines, Could you help with the pseudo-code below:

I have the step count:
Step Count

for i = 1 to n n+1
j = n * 2 n
while j >= 1 n(2n+1)
j = j – 1 n(2n)

So Total step count T(n) = n+1 + n + 2n2 + n + 2n2
= 4n2 + 3n + 1
Thanks in advance!

[apines]

What exactly is j = j – 1 n(2n)? is it 1*n(2n) or perhaps 1+n(2n)?

[amatech]

What exactly is j = j – 1 n(2n)? is it 1*n(2n) or perhaps 1+n(2n)?

Sorry apines here is the pseudo-code

for i = 1 to n
j = n * 2
while j >= 1
j = j – 1

[apines]

You really need to specify where the curly brackets begin and end. Assuming that the code is the more complicated version:

for i = 1 to n 
{
   j = n * 2 
   while j >= 1 
   {
      j = j – 1
   }
}

Then the outer loop iterates from 1 to n, meaning n iterations. The inner loop, at the first outer loop iteration when i=1, will have j=2, and it will go for two iterations until j will no longer be higher or equal to 1. The second outer loop iteration i=2, meaning j=4, and we will have 4 iterations of the inner loop. We can see that for every i=k, we will have j=2k and will do 2k iterations. This will go on until the last iteration where i=n, j=2n and we will have 2n iterations. Overall we will have n(2+4+6+...+2n) = n*(2n+2)n/2 (using the sum of an arithmetic progression again).

[geojia]

There is something wrong. nested loops have worst running time of O(n^2) but you are showing O(n^3).
1. outer for loop runs n times
2. the while loop runs max 2n each time.
.*. worst case n(2n) W(n^2)