= Memoization arithmetic and stack costs
Under constant-cost lookup and <integer> <addition>, <Memoized Fibonacci evaluation> has <time complexity> $O(n)$ in <Big O notation>, retaining $O(n)$ values. A <hash table> needs its own lookup-cost assumptions; an <array> indexed by $0,\ldots,n$ avoids <hash collisions> in this example. <Memoization> removes repeated bodies, but also pays for keys, lookups and retained answers. A workload without reuse can pay those costs without saving evaluations.
The <call stack> remains. Left-first <recursion> descends through arguments $n,n-1,\ldots,1$ before returning, giving $n$ simultaneously active frames for $n\geq2$. Therefore the auxiliary <space complexity> includes $O(n)$ frames as well as $O(n)$ table entries in the constant-size-value model. An iterative bottom-up <dynamic programming> calculation removes these recursive frames; retaining only the two previous <Fibonacci numbers> suffices when only the final value is wanted, but discards the table useful for later requests.
Exact <Fibonacci numbers> do not remain constant-size values. For $k\geq2$, the <recurrence relation> gives $2^{(k-2)/2}\leq F_k\leq2^{k-1}$, so the representation of $F_k$ as a <binary number> has order $k$ <bits>. With ordinary <addition> costing order $k$ <bit> operations on such operands, the $n-1$ <additions> cost order $n^2$ <bit> operations in total. Retaining all values also requires order $n^2$ <bits> of value storage, before keys and frame overhead. The linear bound counts <additions> under its stated cost model; it is not a linear bound on exact <integer arithmetic> in <bits>.<Lecture 15: Recursive Algorithms (6.006 Spring 2020) by Massachusetts Institute of Technology, 6.006 course staff>[MIT 6.006 Spring 2020, Lecture 15: Recursive Algorithms, printed p. 3, final three bullets: growing Fibonacci bit lengths and addition cost]{ref}
Back to article page
