Which of the following is a more appropriate complexity for this reccursive function?

Question

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?

Answer 1

You can show that if the binary expansion of $A>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)$.