What is the complexity of the following code?

Question

According to this code:

for (int i=1; i<=N; i*=2)
{
  for (int j=1;j<=i;j++)
  {
    System.out.println("The value for i is "+i+" and the value for j is "+j);
  }
}

The first for-loopwill run log(n)once, at first I thought about 2n-1for the second for-loop, but it does not work for odd numbers.

Any ideas? :)

Answer 1

Your first for loop got ias a series:

The first loop stops when the last element of this series is greater than or equal to N:

xmeans how many times the first cycle is executed. Now we are trying to find x:

Where

Yes, this is how you say:

The first for-loop will run log (n) times

The second body of the cycle works as the sum:

, O (n)

2N-1 , N : 1, 2, 4, 8, ... , 2^n

---

, .

Answer 2

• i = 1, 1
• i = 2, 2
• i = 4, 4
• ...
• i = N, N

1 + ... + N/4 + N/2 + N , O (n).