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)?