Time Complexity

Question

What is the complexity of the following code?
 

i = n
while (i>=1){
    for j = 1 to n
        x=x +1
    i = i/2
}

1. $\Theta(n)$
2. $\Theta( \log_2 n)$
3. $\Theta( n/\log_2 n)$
4. $\Theta( n \log_2 n)$

Answer 1

The outer while loop runs logn times because every time n is getting divided by 2 ie {n/2 , n/4 , n/8 , ......1 }

For every iteration of outer loop inner loop runs n times .

Therefore the complexity is $\Theta$(nlogn)

Ans : Option D.

Comments

For every value of i j run 1 to n

 So o(n log n) d

Answer 2

Both the loops are independent of each other .

Inner loop always runs for n times and outer loop log₂n times . 

Hence complexity is : O(n log₂n)