Big-O: Why is the time complexity of these loops O(N)?

I have the following function.

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;
}


It has O(N) time complexity. I thought it's O(N LogN)(i.e. If we remove the inner loop we get)

for (int i = n; i > 0; i /= 2){
...
}


This is O(Log N) isn't it? And the inner loop turns out to be O(N) as it just increase linearly. So I think it's supposed to be O(Log N * N). What might go wrong on my thought?

• Mistake: The inner loop is not linear in n. Commented May 27, 2020 at 17:01

1 Answer

Look at how many steps the inner loop is taking. It's $$n + \frac{1}{2}n + \frac{1}{4}n + \cdots$$. However the geometric series tells us:

$$\sum_{k=0}^{\lceil\log n\rceil +c}\frac{n}{2^k} < n\sum_{k=0}^\infty \frac{1}{2^k} = 2n$$

• Thanks. Not related to the correct answer. But for the outer loop, is that O(Log N) right? Commented May 27, 2020 at 13:35
• @Plain_Dude_Sleeping_Alone Yes the outer loop does $\lceil \log n \rceil + c$ iterations (where $c$ is some off-by-one error I'm too lazy to figure out precisely), which is why I put it as the upper bound of the first sum.
– orlp
Commented May 27, 2020 at 13:36