int fun(int n) {
int count = 0;
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1;
return count;
}
I'm a very new to the time complexities calculations. For this algorithm, I get the answer to be O(nlogn), but the answer is apparently O(n).
My logic was the outer loop has an exponential decline and will occur log_base2_(N) times. The inner loop will run a total of N times as it becomes a geometric sum (first iteration it is N/2 times, then N/4, then N/8 ...). If I put these together and multiply them as a result of the nested loop, that's where I'm coming up with O(NlogN). Am I missing something obvious?