0
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Mistake: The inner loop is not linear in n. $\endgroup$
    – gnasher729
    Commented May 27, 2020 at 17:01

1 Answer 1

1
$\begingroup$

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$$

$\endgroup$
2
  • $\begingroup$ Thanks. Not related to the correct answer. But for the outer loop, is that O(Log N) right? $\endgroup$ Commented May 27, 2020 at 13:35
  • 1
    $\begingroup$ @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. $\endgroup$
    – orlp
    Commented May 27, 2020 at 13:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.