Divide & Conquer Algorithms - 3 - Fibonacci Numbers

The formula for Fibonacci numbers is as follows:

\[F(n)=\begin{cases} 1 & \text{if } n=0 \text{ or } 1\\ F(n-1) + F(n-2) & \text{if } n> 1 \end{cases}\]

Pseudo Code

This is a recursive implementation:

Algorithm F(n)
	if n == 0 OR n == 1 then
		return 1
	else
		return F(n-1) + F(n-2)

To analyse the time complexity of calculating Fibonacci numbers, we use a mathematical tool called recurrence.

Let $T(n)$ denote the time to calculate Fibonacci number $F(n)$:

\[T(n)=\begin{cases} 1 & \text{if } n=0 \text{ or } 1\\ T(n-1) + T(n-2) + 1 & \text{if } n> 1 \end{cases}\]

$T(n-1)$: Time to calculate $F(n-1)$.
$T(n-2)$: Time to calculate $F(n-2)$.
$+1$: Time to add $F(n-1)$ and $F(n-2)$.
When $n$ is 0 or 1 there is no needed to divide and the only time needed is to return the number 1.

A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs.

To solve a recurrence is to derive asymptotic bounds on the solution.