Help understanding Recursive algorithm question

Question

We have a function that is defined recursively by $f(0)=f_0$, $f(1)=f_1$ and $f(n+2) = f(n)+f(n+1)$ for $n\geq0$

For $n\geq0$, let $c(n)$ be the total number of additions for calculating $f(n)$ using $f_0$ and $f_1 $ as input with $c(0) = 0$ and $c(1) = 0$. For $n \geq 2$, express $c(n)$ using $c(n-1) $ and $c(n-2)$

Determine if $c(n)\geq2^{(n-2)/2}$ for $n\geq2$ and prove your answer.

I'm lost as to what to do with this question.

Answer 1

Try doing by induction:

Base step: $$ c(2) = 2 \ge 2^{(2-2)/2} = 1$$

Inductive step:

if $c(n) \ge 2^{(n-2)/2} \rightarrow c(n+1) \ge 2^{((n+1)-2)/2}$

You probably need to think the way to calculate how $c(n)$ increases whit each value of $n$

Answer 2

Hint:

$$c(n+2)=c(n+1)+c(n)+1$$

Solve this to get $c(n)$ and prove that $c(n) \ge 2^{\frac{n-2}{2}}$ by induction.

Answer 3

This is a badly formulated problem, the claim is probably wrong.

• If the task is just to compute $f(n)$, then one can use matrix powers as $$ \begin{bmatrix}f(n)\\f(n-1)\end{bmatrix} = \begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1} \begin{bmatrix}f(1)\\f(0)\end{bmatrix} $$ These matrix powers can be computed by halving-and-squaring so that one needs $O(\log_2(n))$ additions and multiplications for the computation of the single value $f(n)$.

• If one wants to compute all of $f(0),f(1),f(2),...,f(n)$, then the step increasing $n$ adds one addition to the computational effort, resulting in $O(n)$, more precisely $(n-1)$, additions.

• Of course, to demonstrate the dangers of blind implementation of recursive functions, the exponential estimate results from the worst possible implementation of the computation of $f(n)$.

See the computation of the Fibonacci-sequence for further details such as complexity in bit-operations.

Answer 4

In reality, only n-1 additions are needed. The only formula that we can use is f(n+2) = f (n+1) + f (n) for n >= 0. If f0 and f1 are given, the only value this formula allows us to calculate is

f2 = f1 + f0 (applying the formula with n = 0)

Now with f2 available as well, the only value the formula allows us to calculate is

f3 = f2 + f1 (applying the formula with n = 1)

and so on.

I'd express the number of additions as

c(n) = c(n−1) + 1

or if you insist on using c(n-2) in the formula then

c(n) = c(n−1) + 1 + 0 * c(n-2)