Fibonacci Algorithm

The Fibonacci algorithm is a one that returns the $n^{th}$ Fibonacci number. The implementation is usually done via recursion.

Pseudocode §

Naïve Recursive:

Algorithm fibonacci(n):
	if n <= 1 then:
		Return n
	End if
	Return fibonacci(n-1) + fibonacci(n-2)
End Algorithm

Dynamic Programming

F ← Array of length n-1
Algorithm fibDP(n):
	if n <= 1 then:
		F[n] = n 
	if F[n] is NOT empty then:
		Return F[n]
	F[n] ← fibDP(n-1) + fibDP(n-2) #Memoization
	Return F[n]

Time Complexity §

Naive Implementation $T(n)=T(n-1)+T(n-2)+c$ where $T(0)=0$ and $T(1)=1$ Here, we know that $T(n-1)>T(n-2)$, so we change the relation to: $T(n)=T(n-1)+T(n-1)+c=2T(n-1)+c$ $T(2)=2T(1)+c$ $T(3)=2T(2)+c=2\ast (2T(1)+c)+c=4T(1)+3c$ $T(4)=2T(3)+c=2(2T(2)+c)+c=2(2(2T(1)+c)+c)+c=8T(1)+7c$ $...T(n)=2^{n-1}\ast T(1)+kc$ Dropping all constants… and we know that T(1) is constant time $=O(2^n)$

Well, actually...

A tighter time complexity is roughly $\Theta (1.7^n)$. Why? I am yet to find out.#tosee