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?

  • $\begingroup$ Mistake: The inner loop is not linear in n. $\endgroup$
    – gnasher729
    May 27 '20 at 17:01

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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