# Time complexity of recurrence function with if statement

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

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

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?

• Your answer is correct, though the argument is of course lacking. Essentially, even odd integers get reduced by 2 in two steps. – Yuval Filmus Mar 21 '19 at 10:47

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