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?
[Math] Time complexity of recursive functions
algorithmsasymptoticsrecursionrecursive algorithms
Related Solutions
Assuming (as Jesko does) that $q$ is a constant and not part of the input, the usual long-division algorithm you learn at school will do quite nicely. The algorithm is the following:
Compute multiples $q$, $2q$, $3q$, $4q$, $\dots$, $10q$. This takes constant time, as it's independent of $q$.
Say $q$ has $k$ digits. Start with the first $k$ digits of $p$. Call this string $s$.
Compare it against each of the $10$ multiples of $q$; whichever $cq$ is the largest one smaller than $s$, write down $c$ as a digit of answer, subtract $cq$ from $s$, and "bring down" the next digit of $p$. That is, set $s$ to be $(s - cq)$ concatenated with the next digit of $p$.
If $s < q$, then it's your answer, stop. Else, go back to step $3$ and repeat.
Here's an image from Wikipedia, for the example of $q = 37$.
Multiplication in bit level can be as easy as shifting bits which is $O(m)$. This is the case of $a=2^k$. (Note here the bit level arithmetic that left-shift is equivalent to multiplying by 2. $m$ here is the number of bits.) Or, plain shifting-and-adding and that's in $O(m^2)$.
If you are performing $a^n$ as plain multiplication of $a^{i-1} \times a$ in as many as those $n-1$ steps it takes, then the complexity becomes $O(m^3)$ in the worst case and is $O(m^2)$ in the best-- the case of $a=2^k$.
Best Answer
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 $$