Use a recursion tree to determine a good asymptotic upper bound for the function $T(n) = 2T(n−2)+1$ 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?
 A: 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$.
A: 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.
A: 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)$.
