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!

amatech
0
Newbie Poster

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!

Jump to PostAssuming 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, …

Jump to PostYou 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 …

apines
116
Practically a Master Poster
Featured Poster

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
0
Newbie Poster

Thanks apines, very good explanation. this helped alot!

Best regards!

apines
116
Practically a Master Poster
Featured Poster

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

amatech
0
Newbie Poster

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
116
Practically a Master Poster
Featured Poster

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

amatech
0
Newbie Poster

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
116
Practically a Master Poster
Featured Poster

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
0
Junior Poster in Training

1. outer for loop runs n times

2. the while loop runs max 2n each time.

.*. worst case n(2n) W(n^2)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.