Fibonacci Algorithm

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

Pseudocode §

Naïve Recursive: §

Algorithm Fibonacci(n: Integer):
	If n <= 1 then:
		Return n
	End if
	Return Fibonacci(n-1) + Fibonacci(n-2)
End Algorithm

Simple Dynamic Programming: §

Using memoization in dynamic programming:

Algorithm FibDP(n: Integer):
	F <- Array of length n
	F[0] <- 1
	F[1] <- 1
	For i from 2 to n do://Theta(n)
		F[i] <- F[i-1] + F[i-1]
	End do
	Return F[i]
End Algorithm

Improved Dynamic Programming (Lesser Storage) §

Algorithm FibDP(n: Integer):
	nMinus1 <- 1
	nMinus2 <- 1
	nCurrent <- 1
	For i from 2 to n do:
		nCurrent <- nMinus1 + nMinus2
		nMinus2 <- nMinus1
		nMinus1 <- nCurrent
	End do
	Return nCurrent
End Algorithm

Time Complexity §

Naïve Recursive §

Using a Recursion Tree:

Note, here we assume that $n-2$ is always lesser than $n-1$, so we can treat it as $n-2=n-1+c$

%%🖋 Edit in Excalidraw, and the dark exported image%%

The total cost per level is given by:

$$2^i(n-i)$$

We reach the base case ($\text{Cost}=1$) when $i=n-1$:

2^{n-1}(n-(n-1)) = 2^{n-1}\cdot_{1} \in \Theta(2^n)$$ >[!info] Well, actually... > >A tighter time complexity is roughly $\Theta(1.7^n)$. Why? I am yet to find out. #TOSEE ##### DP (Both) Because the outer loop runs $n-2$ times, we have the time complexity bounded in

\Theta(n)

The difference between the two implementations is one has a space complexity of $\Theta(n)$ and the other has a space complexity of $\Theta(1)$