Aside from using an equation to calculate the nth Fibonacci number, the following iterative method has the best time and space complexity.

Time complexity is \(O(n)\) and space complexity is \(O(1)\). This method saves on space, since we only need to store the previous two Fibonacci numbers.

func fib(_ n: Int) -> Int? {
  if n < 1 { return nil }
  if n < 3 { return 1 }
  
  var i = 1
  var ii = 1
  var an = 0
  
  for _ in 3...n {
    an = i + ii
    ii = i
    i = an
  }
  
  return an
}

Leave a Reply

Come See Me

San Francisco, CA
hello@ingax.com

See My Work