1
$\begingroup$

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?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.