Big-O: Why is the time complexity of these loops O(N)?
-
29-09-2020 - |
Question
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?
Solution
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$$
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange