# Time complexity of recursive functions

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?

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