2b. Fibonacci

$F(n)=F(n-2)+F(n-1)$ if $n\ge 2$

Idea 1: Recursion

• case 0: return 0
• case 1: return 1
• else return F(n+1)+F(n+2) Absolutely atrocious implementation that grows exponentially with n. Would take forever to compute answer.

Idea 2: Array F of length

F[0] = 0
F[1] = 1
for i = 2 to n:
	let F[i] = F[i - 1] + F[i - 2]

O(n) or polynomial time. Way faster as ignores repeated calls. Operates off of the principles of the Fibonacci problem.

• Is this a dynamic programming solution with memoization? Kinda looks like it.

NOTE

While the loop runs in $O(n)$, the bit operations of adding two numbers increase the total running time to $O(n^2)$ in terms of total computer steps. This is because adding two n-bit numbers takes $O(n)$ time.