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?