Running time analysis of Fibonacci algorithm.

Question

I am getting the following statement:

Code

RecFibo(n):
if (n < 2)
  return n
else
  return RecFibo(n − 1) + RecFibo(n − 2)

From text:

Another way to see this is that the RecFibo is building a big binary tree of additions, with nothing but zeros and ones at the leaves. Since the eventual output is Fn , our algorithm must call RecRibo(1) (which returns 1) exactly Fn times. A quick inductive argument implies that RecFibo(0) is called exactly Fn−1 times. Thus, the recursion tree has Fn + Fn−1 = Fn+1 leaves, and therefore, because it’s a full binary tree, it must have 2Fn+1 − 1 nodes.

Further

A quick inductive argument implies that RECFIBO(0) is called exactly Fn−1 times. Thus, the recursion tree has Fn + Fn−1 = Fn+1 leaves, and therefore, because it’s a full binary tree, it must have 2Fn+1 − 1 nodes.

Although I understand and can visualize the recursive tree but the induction analysis leaves me puzzled. My main confusion is the most obvious part from the author claiming "our algorithm must call RecFibo(1) (which returns 1) exactly Fn times" and same for "RecFibo(0)".

Reference:

http://jeffe.cs.illinois.edu/teaching/algorithms/notes/05-dynprog.pdf

Answer 1

If (by the inductive hypothesis)

• in calculating RecFibo(n-1) you call RecFibo(1) $F_{n-1}$ times and RecFibo(0) $F_{n-2}$ times
• in calculating RecFibo(n-2) you call RecFibo(1) $F_{n-2}$ times and RecFibo(0) $F_{n-3}$ times

then in calculating RecFibo(n) by calling RecFibo(n-1) and RecFibo(n-2) you call RecFibo(1) $F_{n-1}+F_{n-2}=F_{n}$ times and RecFibo(0) $F_{n-2}+F_{n-3}=F_{n-1}$ times

You should probably also show the hypothesis is true for RecFibo(2) and either RecFibo(3) or RecFibo(1)

This is not the most efficient algorithm

Answer 2

Lets use the notation from your notes. So we define $T(n)$ as the number of recursive calls of $RecFib$. We first note that $$T(0)=1 \text{ and } T(1)=1.$$ This is easy to see, since we fulfill the condition of the "if" and do not call the function $RecFib$ again. Next we observe that for $n\ge 2$ $$T(n)=T(n-1)+T(n-2)+1.$$ For this note that we once have to call the function itself and then since $n\ge 2$ we call the function $RecFib$ again but with inputs $n-1$ and $n-2$, contributing the terms $T(n-1)$ and $T(n-2)$.

Claim: $T(n)=2F_{n+1}-1$.

Proof: We proceed here by induction. The cases $n \in \{0,1\}$ should be clear. So lets assume the induction hypothesis holds for $n'$ with $0 \le n' <n$. Lets compute $T(n)$ using the induction hypothesis in the second equality: $$ T(n)=T(n-1)+T(n-2)+1=(2F_n -1 )+ (2F_{n-1}-1)+1=2(F_n+F_{n-1})-1=2F_{n+1}-1.$$