Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$? In my analysis of algorithms class we were given the following recurrence relation:
\begin{eqnarray}
T(n) &amp;=&amp;
\begin{cases}
    T\left(\displaystyle\frac{n}{2}\right) + 1, &amp;n \ \mbox{is even number}&amp; \\
    2T\left(\displaystyle\frac{n-1}{2}\right),　&amp;n \ \mbox{is odd number}&amp;
\end{cases} \nonumber \\
T(1) &amp;=&amp; 1
\end{eqnarray}
I have proved by iteration (expand) that when $n = 2^k$ (always the even case), $T(n) = O(\log{n})$; when $n = 2^{k+1}-1$ (always the odd case), $T(n) = \Omega(n)$.
Is this actually possible? After looking at some other posts, I am thinking this is possibly because the $\Omega(n)$ obtained here is the lower bound runtime of the worst case scenario, and the $O(\log{n})$ is the upper bound runtime of the best case?
Am I confusing something? Or is there any other conclusion can be drawn from the result that $T(n) = O(\log{n})$ and $T(n) = \Omega(n)$ for the recurrence?
You calculated “Big-Theta for n = power of two - 1”. That’s not a useful thing. Try calculating T(n) for n = (4^k - 1) / 3 and be surprised. (Write n down in binary first). Or n = 3 * (8^k - 1) / 7 where T(n) ≈ n^(2/3).
You found the values for a good case and for a bad case. You’ll have to prove they are lower and upper bound.