I want to solve the following recursion to find the complexity.
$f(n)=\begin{cases} 2f(n/2) + n^2 & \textbf{if } n \text{ is even}\\ 2f(\lfloor n/2\rfloor) + n^3 & \textbf{if } n \text{ is odd} \end{cases} $
It is clear that
- if $n=2^k$ (10000...000) for some $k>1$ the answer is $\mathcal{O}(n^2)$
- if $n=2^k-1$ for some $k>1$ the answer is $\mathcal{O}(n^3)$
The bits of the $n$ determines the complexity.
So exactly when it is $\mathcal{O}(n^2)$ or $\mathcal{O}(n^3)$