Time complexity of recurrence function with if statement

Question

Given the following code.

public static int fc(int n, int p) {
    if (p == 0) {
        return 1;
    } if (p % 2 == 0) {
        int a = fc(n, p / 2);
        return a * a;
    } return n * fc(n, p - 1);
}

How to calculate the time complexity of this code in big-$\mathcal{O}$ notation? I already define the recurrence function, which is

\begin{equation} T(p) = \begin{cases} 1, & \text{if}\ p=0 \\ T(p/2) + 1, & \text{if } p \text{ is even} \\ T(p-1) + 1, & \text{if } p \text{ is odd} \end{cases} \end{equation}

Assuming that $p = 2^k$, then $T(p) = T(2^k) = T(2^{k-1}) + 1$. By backwards substitution, the equation become $T(2^k) = T(2^{k-n}) + n$. When $k = n$, $T(2^k) = T(1) + k = 1 + \log p$. Thus, $T(p) = \mathcal{O}(\log p)$.

However, I think that it only holds for the best case. I want to know about the other cases as well. How do I prove the average and worst case for this code?

Answer 1

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 < 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 < 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}}. $$