Which of the following is a more appropriate complexity for this reccursive function?
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)$.