# Complexity of T(n)=2T(n-1)

I built a recursion tree like this:

  0
/ \
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)$$?

• 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. Commented Jun 7, 2022 at 17:54
• The title of the post is wrong. And there is no connection between the width $2^n$ and $\sum_{i=0}^n$.
– user16034
Commented Jun 7, 2022 at 19:47
• "is the function $O(1)$ ?": which function ??
– user16034
Commented Jun 7, 2022 at 19:51
• 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. Commented Jun 8, 2022 at 1:22

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