Which of the following is a more appropriate complexity for this reccursive function? Given the following recurrence relation:
\begin{gather*}
h(A) =
\begin{cases}
  0,\qquad \qquad \text{ }\text{ }\text{ }A=0\\    
  1+h(A-1),\text{ }\text{ }A\text{ is odd} \\
  1+h(\frac{A}{2}),\qquad \text{otherwise}
\end{cases}
\end{gather*}
which of the following choices best describes its complexity?
A) $h(A)\in\theta(\log_2A)$
B) $h(A)\in\Omega(\log_2A),\text{ }h(A)\in\mathcal{O}(A)$
The book that I'm reading has selected choice $A$, however I feel like $B$ should be the answer. We know that the complexity is at minimum $\log_2A$ (best case when it's a power of $2$), but it could be higher than that and have a few more steps depending on what $A$ is. What am I missing here?
You can show that if the binary expansion of $A&gt;0$ contains $N_0$ zeroes and $N_1$ ones then $h(A) = 2N_1 + N_0$. Since $N_0 + N_1 = \lfloor \log_2 A \rfloor + 1$, this shows that $h(A) = \Theta(\log A)$.