# 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>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)$$.