4 ms·
...which makes it a classic exercise for teaching memoization!
by elseweather 6y ago
...which makes it a classic exercise for teaching memoization!
- astine 6y agoAnd now your memory usage will grow eye-wateringly large. Instead, convert the algorithm to be iterative or at least tail-recursive and it will be faster than both the naive and memoized versions!
- karamazov 6y agoOr use the closed-form solution.
- jacobolus 6y agoThe "closed-form solution" is slower than standard method. It just uses arbitrary-precision fractional arithmetic (square root, exponentiation, division) instead of arbitrary-precision integer arithmetic (exponentiation of a 2x2 integer matrix).
- singhrac 6y agoThe best solution is to use the O(log n) time exponentiation of a matrix, which is fast enough to be constant.