I attempted to write an \$O(N)\$ Fibonacci.fibMemo :: Integer -> Map Integer Integer -> IntegerfibMemo n map | n == 0    = 0 | n == 1    = 1 | otherwise = case maybeMember of Just x  -> x                                   Nothing -> calced               where maybeMember = M.lookup n map                     calced      = fibMemo (n-1) map + fibMemo (n-2) mapMy understanding is that it's \$O(N)\$ since I think, worst case, it takes \$N\$ calls to fibMemo in order to compute fibMemo(N).Please critique my Haskell implementation, as well as answer the O(N) question.
O(n) Fibonacci?
haskell;reinventing the wheel;fibonacci sequence
You're not caching the results, so fibMemo is \$O(2^n)\$.More precisely, fibMemo n will result in \$2F_{n + 1} - 1\$ calls to fibMemo, where \$F_n\$ is the \$n\$th Fibonacci number.To prove this, let \$T(n)\$ be the total number of calls to fibMemo required to evaluate fibMemo n. Then\begin{align}T(0) &= 1 = 2F_1 - 1, \\T(1) &= 1 = 2F_2 - 1,\end{align}which are our base cases. In the general case,\begin{align*}T(n + 1) &= 1 + T(n) + T(n - 1) \\     &= 1 + (2F_{n + 1} - 1) + (2F_{n} - 1) \quad \text{(by the induction hypothesis)} \\     &= 2(F_{n + 1} + F_{n}) - 1 \\     &= 2F_{n + 2} - 1.\end{align*}You can get timing information using :set +s in GHCI, which gives a pretty strong hint that it's not \$O(n)\$:*Main> :set +s*Main> fibMemo 20 M.empty6765(0.08 secs, 18282888 bytes)*Main> fibMemo 30 M.empty832040(3.81 secs, 1092375120 bytes)