I built a recursion tree like this:

 / \  
 0  0  
/\ /\  
... ...

So the tree has height n, and width $2^n$. But if the sum of all levels is $\sum_{i=0}^{n}0$, then is the function simply $O(1)$?

  • $\begingroup$ You are missing the base cases from your recurrence relations. I suspect it is $T(1)=1$. You might want to redraw the tree with this in mind. $\endgroup$
    – Steven
    Commented Jun 7, 2022 at 17:54
  • $\begingroup$ The title of the post is wrong. And there is no connection between the width $2^n$ and $\sum_{i=0}^n$. $\endgroup$
    – user16034
    Commented Jun 7, 2022 at 19:47
  • 1
    $\begingroup$ "is the function $O(1)$ ?": which function ?? $\endgroup$
    – user16034
    Commented Jun 7, 2022 at 19:51
  • $\begingroup$ Maybe you're thinking of $T(n)=2T(n-1) + 0$. The problem, like @Steven says, is that you need a base case. To see it even more clearly than your illustration, simply try rewriting the function. For example, write $T(n)=2T(n-1) + 0 = 2(\underbrace{ 2T(n-2)+0 }_{T(n-1)}) + 0 = 2( 2(\underbrace{2T(n-3)+0}_{T(n-2)}) + 0 ) + 0 = \dots$. Eventually, you will still need the function $T(n-k)$ for some $k$. This function, $T(n-k)$, doesn't need to be constant. i.e. it could be a function of $n$. It could also be $0$, which is even faster than a constant function. $\endgroup$
    – Matt Groff
    Commented Jun 8, 2022 at 1:22

1 Answer 1


A sum of $m$ constants takes time $O(m)$.


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.