Fibonacci sequences within the Fibonacci sequence recurrence

algorithmsfibonacci-numbersrecurrence-relations

I'm trying to perform a runtime analysis of the following simple recursive Fibonacci number algorithm:

Fibonacci(n) {
    if n < 0 return -1
    else if n == 0 return 0
    else if n == 1 return 1
    else return Fibonacci(n - 1) + Fibonacci(n - 2)
}

Define the "$T(i)$ count" for $n$ to be the number of times $T(i)$ is evaluated by the algorithm when evaluating $T(n)$.

In breaking down the formulas for smaller values of $n$, I found the following to be true:

$n$ $T(1)$ count $T(0)$ count
0 0 1
1 1 0
2 1 1
3 2 1
4 3 2
5 5 3
6 8 5
7 13 8

Note: $T(1)$ is the run time of the above algorithm when $n = 1$, and $T(0)$ is the run time of the algorithm when $n = 0$. Specifically, $T(1), T(0)\in \Theta(1)$.

The trend in the counts of $T(1)$s and $T(0)$s seems like they follow the Fibonacci sequence themselves:

  • The number of $T(1)$s making up the run time of the $n^{\text{th}}$ Fibonacci number is the $n^{\text{th}}$ Fibonacci number itself, $F_n$.
  • The number of $T(0)$s making up the run time of the $n^{\text{th}}$ Fibonacci number is the $(n – 1)^{\text{th}}$ Fibonacci number, $F_{n-1}$, except for $F_0$ which has one $T(0)$ in its run time (I noticed that for $n = 0$ the number of $T(0)$s is the same as the number of $T(0)$s when $n = 2$ minus the number of $T(0)$s when $n = 1$, i.e., $T(0)$ count = $T(2)$ count $ – \text{ } T(1)$ count).

This would mean that

$$T(n) = F_n \times T(1) + F_{n – 1} \times T(0) \in \Theta\left( F_n \right) \cup \Theta\left( F_{n-1} \right) = \Theta\left( F_n \right)$$

for $n \geq 1.$

I guess my only question regarding the work above is to ask someone if it's accurate. I'm very excited by this, so I'm hoping it's correct.

Thank you for your time, attention, and patience (I'm not sure if this is entirely in compliance with the rules, but I'm so amazed by this that I honestly just wanted to share it and determine if I'm right).

Best Answer

This is correct, by induction. We see that the count of Fibonacci(1) evaluations is $F_n$ for $n=1,2$. Then assuming the (strong) inductive hypothesis that Fibonacci(k) evaluates Fibonacci(1) $F_k$ times for $0<k<n$, we see from the line return Fibonacci(n - 1) + Fibonacci(n - 2) that Fibonacci(n) evaluates Fibonacci(1) $F_{n-1} + F_{n-2} = F_n$ times, and similarly counts of evaluations of Fibonacci(0) obeys the Fibonacci recurrence relation. Similarly, for any $i$ we see that eventually (after some initial conditions) the count of Fibonacci(i) evaluations obeys the Fibonacci recurrence.

Related Question