Use a recursion tree to determine a good asymptotic upper bound for the function $T(n) = 2T(n−2)+1$

Question

I'm trying to schematize this type of exercise : Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 2T(n−2)+1$. To do this I made this table :

$$\begin{array}{c|c|} & \text{Levels} & \text{Dimension} & \text{Cost of each node at level i} & \text{Number of nodes at level i} & \text{Level cost} \\\ & 0 & n & 1 & 2^0 & 2^0 \\\ & 1 & n-2 & 1 & 2^1 & 2^1 \\\ & 2 & n-4 & 1 & 2^2 & 2^2 \\\ & . & . & . & . & . \\\ & . & . & . & . & .\\\ & i & n-(2^i-2) & 1 & 2^i & 2^i \\\ & . & . & . & . & .\\\ & . & . & . & . & .\\\ & \log_2 (1+n) & 1 & T(1) & 2^{log_2 (1+n)} = (1+n)^{log_2 (2)} = (1+n) & (1+n) \end{array}$$

Now adding the "Level cost" column up to the penultimate row and adding the last row of the table we get

$$\sum_{i=0}^{\log_2 (n)} 2^i + O(n) = \frac{2^{\log_2 (n)}-1}{2-1} + O(n) = 2^{\log_2 (n)}-1 + O(n) = O(2^{\log_2 (n)}) + O(n) = O(n) $$

Is this the right solution? $T(n) = O(n)$

This sounds strange to me, since I know that the following equation: $T(n)=2T(n−1)+1$ has this as a solution: $T(n)=O(2^n)$. I do something wrong?

Answer 1

Your mistake is calculating the wrong depth for the tree: the depth is not $\log_2(n+1)$. As this seems like a homework assignment, I'll give a hint instead of the direct answer:

The recurrence relation is $T(n) = 2T(n-2)+1$, i.e. we start from $n$ and then subtract 2 repeatedly until we reach one of the base cases, $T(0)$ or $T(1)$. How many times do you subtract 2 from $n$ before you reach 0 or 1? Certainly not $\log_2(n+1)$ times: you are subtracting, not dividing by two.

Once you correct the tree depth, you can calculate the closed form for $T(n)$ by correctly evaluating the sum over all the nodes.

Answer 2

Actually what led me to make a mistake was evaluating that at ith level there are $2^$ nodes each of dimensions $−(2^−2)$ (by dimension I mean the size of the input given to the recursive function) . This for example is not true at level 0. Where if this were true we would have $n-(2^0-2) = n+1$. When instead at level 0 the dimension is n. The correct dimension is instead this : $(n-2*i)$. This works for every level i. Now thanks to this I can answer the question : for what value of i, $(n-2*i)=0 $? the answer is $i=n/2$. This is the number of times you need to subtract 2 from until you reach $T(0)$. So

$$()=1+2(−2)=1+2(1+2(−4))=1+2+4(−4)=1+2+4(1+2(−6))=1+2+4+8(−6)=…=(2^{/2}−1)+2^{/2}(0)=Θ(2^{/2})$$

Surely this is a very strict limit. To prove that it was true, one would have to use the substitution method. Keeping wide, I think we can say that $T(n)=O(2^n)$.

Answer 3

In this case the exact solution is quite straightforward to determine compared to any other method since you can rewrite the relation: $$\overbrace{T(n)+1}^{U_n}=2T(n-2)+2=2\Big(T(n- 2)+1\Big)$$

And you get $U(n)=2U(n-2)$ leading to $U_{2n}=2^nU_0$

Generally in cost studies we are assuming some homogeneity between $U_1$ and $U_0$ and not separate branches for odd and even values of $n$ and we (kinda abusively) write $$U_n=2^{n/2}U_0$$

In theory we could have $\begin{cases}U_{2n}=2^nU_0\\U_{2n+1}=2^nU_1\end{cases}$ but this leads anyway to $U_n=\mathcal O(2^{n/2})$ the constants $U_0,U_1$ being absorbed by the $\mathcal O$.

And of course subtracting $1$ to $U_n$ doesn't change the estimation for $T_n$.