Solving recurrence relation for asymptotic analysis
Suppose $n = 2^m + 1$. Then
$$
T(n) \geq 2T(2^{m-1}+1) \geq 4T(2^{m-2}+1) \geq \cdots,
$$
and so $T(n) = \Omega(n)$ for $n$ of this form. Therefore you cannot get a better worst-case bound than $O(n)$.

In more detail, this example shows that if $T(n) = O(f(n))$ for a monotone function $f(n)$ then $f(n) = \Omega(n)$. You might be able to get an upper bound using more information on $n$.



Let's analyze a similar but slightly simpler recursion,
$$
S(n) = \begin{cases} S(n/2) + 1 &amp; \text{if $n&gt;0$ is even}, \\ 2S(\lfloor n/2 \rfloor) + 1 &amp; \text{if $n$ is odd},\\ 0 &amp; \text{if $n = 0$}. \end{cases}
$$
Let us denote
$$
S(a_1,\ldots,a_k) = S(2^{a_1} + \cdots + 2^{a_k}),
$$
where we implicitly assume that $a_1 &gt; \cdots &gt; a_k$. We have
$$
\begin{align*}
S(a_1,\ldots,a_k) &amp;= 1 + S(a_1-1,\ldots,a_k-1) \\ &amp;=
2 + S(a_1-2,\ldots,a_k-2) \\ &amp;= \cdots \\ &amp;=
a_k + S(a_1-a_k,a_2-a_k,\ldots,a_{k-1}-a_k,0) \\ &amp;=
a_k + 1 + 2S(a_1-a_k-1,a_2-a_k-1,\ldots,a_{k-1}-a_k-1) \\ &amp;=
(a_k + 1) + 2(a_{k-1}-a_k) + 4S(a_1-a_{k-1}-1,\ldots,a_{k-2}-a_{k-1}-1) \\ &amp;=
(a_k+1) + 2(a_{k-1}-a_k) + 4(a_{k-2}-a_{k-1}) + \cdots + 2^{k-1}(a_1-a_2) \\ &amp;=
2^{k-1} a_1 - 2^{k-2} a_2 - \cdots - a_k + 1.
\end{align*}
$$
Notice now that
$$
2^{k-1} a_1 - 2^{k-2} a_2 - \cdots - a_k + 1 \geq \\
2^{k-1} a_1 - 2^{k-2} (a_1 - 1) - \cdots - (a_k - (k-1)) + 1 = \\
a_1 + 2^k - k,
$$
and on the other hand,
$$
2^{k-1} a_1 - 2^{k-2} a_2 - \cdots - a_k + 1 \leq \\
2^{k-1} a_1 - 2^{k-2} (k-2) - 2^{k-3} (k-3) - \cdots - 0 + 1 = \\
2^{k-1} (a_1 - k + 3) - 1.
$$
This gives us a lower bound of $\Omega(\log n + 2^{|n|})$ and an upper bound of $O(n)$, where $|n|$ is the Hamming weight; note that if $n = 2^m-1$ then the lower bound is linear in $n$. Indeed,
$$
S(2^m-1) = 1 + 2S(2^{m-1}-1) = 1 + 2 + 4S(2^{m-2}-1) = \cdots = \\ 1 + 2 + 4 + \cdots + 2^{m-1} S(1) = 2^m-1.
$$



It is likely that you can find a similar formula for $T$.