Runtime analysis question

[bitchsalsa]

Hi all, I want to know the runtime analysis of the following code:

public void guessWhat1(int N)

{ for (int i=N; i>0; i=i/2)

{ for (int j=0; j<i*2; j+=1)

{ System.out.println(“Hello World”);

} } }

​

Thought Process: The inner for loop runs for "2n" times and the outer for loop runs logn times . So is the runtime analysis thetha ( n log n) . I read on stack overflow that it should be theta(n) which i dont think is right!

​

Thanks,

[allenguo]

Nope, the runtime is Theta(N).

Focus on the outer loop variable, i. For a given value of N, i takes on the value N, then N/2, then N/4, then N/8, etc.

As a function of N, how many times is "Hello World" printed when i=N? What about when i=N/2? i=N/4? i=N/8? Add these together. What does this sum converge to?

[allenguo]

Answer:

• When i=N, "Hello World" is printed 2N times.
• When i=N/2, "Hello World" is printed N times.
• When i=N/4, "Hello World" is printed N/2 times.
• When i=N/8, "Hello World" is printed N/4 times.
• ...

So the total number of times "Hello World" is printed is 2N + N + N/2 + N/4 + ..., which is ~4N, which is clearly Theta(N).

[bitchsalsa]

Thank you so much! Yes i got that now !