Time complexity of memoized fibonacci

Question

I recently came across this Haskell memoized fibonacci implementation:

fibonacci :: Int -> Integer
fibonacci = (map fib [0 ..] !!)
  where fib 0 = 0
        fib 1 = 1
        fib n = fibonacci (n - 1) + fibonacci (n - 2)

I'm wondering about the time complexity for generating the nth fibonacci number the first time. Is it O(n^2) because of the list lookups in Haskell? If yes, then is there a way to somehow make it O(n) like in languages with where the lookup operation is O(1)?

Answer 1

Is it O(n^2) because of the list lookups in Haskell?

Yes.

If yes, then is there a way to somehow make it O(n) like in languages with where the lookup operation is O(1)?

The most trivial way would be to use lazy arrays, which do have O(1) random access. This means, you'll have to specify an array size, so you no longer have an infinite sequence, but you have that same limitation in other languages. For example, you could do it like this using Data.Vector:

import Data.Vector

fibsUpto100 :: Vector Integer
fibsUpto100 = generate 100 fib
    where fib 0 = 0
          fib 1 = 1
          fib n = fibsUpto100 ! (n-1) + fibsUpto100 ! (n-2)

Due to laziness nothing will be calculated until an element of the vector is evaluated, at which point all the previous elements of the vector (that haven't been evaluated before) are also evaluated. Once evaluated, each value is stored in the vector, so nothing is evaluated more than once.

Of course it would be nicer to have an infinite list of numbers. One way to achieve this is to translate the standard O(n) way of calculating the nth Fibonacci number (using a while loop that keeps track of the current and previous element) to a recursive Haskell function and then adjusting that to store each element in a list.

The basic translation of the while loop would be:

fib 0 = 0
fib n = fibHelper n 0 1
  where
    fibHelper 0 _ current = current
    fibHelper n previous current =
        fibHelper (n-1) current (current + previous)

Adjusting this to keep a list, we get:

fibs = 0 : genFibs 0 1
  where
    genFibs previous current =
        current : genFibs current (current + previous)

Another, more concise¹ way to achieve the same thing would be to define the list using its own tail. That is we want each element of the list to be the previous element + the element before that and we implement this by taking the list and its tail, adding them together and feeding the result back into the list. This leads to the following definition:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Here 0 and 1 are the first and second element respectively and then the remaining elements are in the list produced by zipWith (+) fibs (tail fibs). The first element of that list (i.e. the third element of the entire list) would be the first element of fibs + the first element of tail fibs, so 0 + 1 = 1, the next element would be 1 + 1 = 2 and so on. So this definition does in fact produce the Fibonacci sequence.

---

¹ Albeit perhaps less understandable to people not too used to tie recursive knots in their heads.

Answer 2

This runs in O(n) time.

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
fibonacci = (fibs !!)