Time complexity of recurrence function with if statement
Let us prove by induction the following formula:


  $T(n)$ is the number of 0s in the binary representation of $n$, plus twice the number of 1s.


This certainly holds for $n = 0$. If $n$ is even, then $T(n) = T(n/2) + 1$, and indeed the binary representation of $n/2$ differs from that of $n$ by having one less 0. If $n$ is odd, then $T(n) = T(n-1) + 1$, and indeed the binary representation of $n-1$ differs from that of $n$ by having one 1 replaced by 0.

This shows that $T(n) = O(\log n)$. It is not clear what you mean by average case, but the formula above should let you work that out. For example, let us consider the $2^{m-1}$ numbers of length exactly $m$. Each of them has a leading 1, and the other $n-1$ bits are half 0, half 1 (considering all numbers in the range). Hence the average value of $T$ for $2^{m-1} \leq n &lt; 2^m$ is $m + 1 + \frac{m-1}{2} = \frac{3m+1}{2}$. Using this, we can compute the average value of $T$ for $0 \leq n &lt; 2^m$ to be
$$
\frac{T(0)}{2^m} + \sum_{\ell=1}^m 2^{\ell-1-m}\frac{T(2^{\ell-1}) + \cdots + T(2^\ell-1)}{2^{\ell-1}} =
\frac{1}{2^m} + \sum_{\ell=1}^m 2^{\ell-1-m} \frac{3\ell+1}{2} = \frac{3}{2}m - 1 + \frac{1}{2^{m-1}}.
$$