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!
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!
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)).
Thanks apines, very good explanation. this helped alot!
Best regards!
Glad I could help you :) Please mark the thread as solved.
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!
What exactly is j = j – 1 n(2n)? is it 1*n(2n) or perhaps 1+n(2n)?
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
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).
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)