1
$\begingroup$

I am trying to derive the number of times * is performed in the following function.

int f(n) {

    if (n == 1)

         return 2*3;

    else

         return f(n-2)*f(n-2)*f(n-2);

}

Can someone help me in deriving this?

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $T(n)$ be the number of times $*$ is performed in evaluating $T(n)$. The base case is easy enough; for any other case, we must first evaluate $f(n-2)$ 3 times (incurring $3T(n-2)$ multiplications) and then two multiplications to put everything together. Hence,

$$T(1) = 1$$

$$T(2k+1) = 3T(2k-1) + 2$$

We may solve this recurrence to get $$T(2k+1) = \frac{2}{3} 3^{k+1} - 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.