Fibonacci Numbers

A mathematical series of numbers as Fibonacci numbers as to provide a foundation for building a Golden ratio number, could be computed in a recurrence relation:

Given function Fn to denote the nth position of a Fibonacci sequence; And,

F1 = F2 = 1; Fn = Fn-1 + Fn-2

A Naive Algorithm

By adopting top-down recursive approach,

FIBONACCI(n)
  if n ⩽ 2 return 1
  else
    return FIBONACCI(n-1) + FIBONACCI(n-2)

which comes down to a recurrence relation: Τ(n) = Τ(n-1) + Τ(n-2) + Ο(1) ⩾ ϕn

Τ(n) ⩾ 2 ⋅ Τ(n-2) + Ο(1) ⩾ 2n/2

Hence, it takes exponential time to compute the nth fibonacci number, wherein lots of repetitive computations are being performed; Specifically in the following diagram,

Figure 1. Fibonacci Numbers in Recursive Computations

To improve upon that, a memoized version of such algorithm is introduced:

memo := {}
FIBONACCI(n)
  if n in memo
    return memo[n]
  else
    if n ⩽ 2 return 1
    else
      memo[n] := FIBONACCI(n-1) + FIBONACCI(n-2)
      return memo[n]

Therefore, FIBONACCI(k) only takes one recursion, ∀ k ∈ n; and all memoized calls use Θ(1) time. Thus, the time complexity is Ο(n), space complexity is Ο(1)

What about we don't want to have recursions? Then, we can use an extra linear space to store the FIB(n - 1) and FIB(n - 2) when computing FIB(n), which is to use iteration in replacement of recursion and having the same time complexity but avoid the use of recursion, which is also called bottom-up DP.

FIBONACCI(n)
  fib := {}
  for k in 1...n
    if k ⩽ 2
      f = 1
    else
      f = fib[n - 1] + fib[n - 2]
    fib[k] = f
  return fib[n]