Find the time complexity of the given code.
int count = 0;
for (int i = N; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count++;
For this snippet the complexity is given to be O(n) but the second loop never runs as i will be zero when the second loop starts, so the complexity should be O(logn).Please see whether I am right or not.
Your analysis is wrong.
I the first loop i iterates from N to 0 and halving every time. So i goes like
N , N/2, N/4 , N/8 < … till 0
Now check j loop with respect to i as there is dependency in both the loop
j goes from 0 to i
When i = N => j = 0 to N -----> Time O(N)
When i = N/2 => j = 0 to N/2 ------> Time O(N/2)
When i = N/4 => j = 0 to N/4 ------> Time O(N/4)
…
So on
So total complexity comes out to be summation of all these individual loops
O(N) + O(N/2) + O(N/4) …
Which is N. Use GP.
Please use a pen and paper and try to understand the above explanation.
Hope it helps.