What is time complexity of following code
int count = 0;
for (int i = N; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
count += 1;
}
} int count = 0;
for (int i = N; i > 0; i /= 2) {
for (int j = 0; j < i; j++) {
count += 1;
}
}At first sight it seems like O(N log(N)) at worst, because the outer loop does log(N) iterations.
But you can actually get tighter. The number of inner loop iterations is
N + (N/2) + (N/4) + ... + 1
<= N + (N/2) + (N/4) + ...
= N (1 + 1/2 + 1/4 + ...)
= N 2
iterations <= 2N.