3 ms·
Everybody seems to forget that addition in exact (arbitrary-precision) arithmetic is not O(1), so the "O(n)" solution is no longer O(n).
by zvrba 13y ago
Everybody seems to forget that addition in exact (arbitrary-precision) arithmetic is not O(1), so the "O(n)" solution is no longer O(n).
- crntaylor 13y agoFair point! It's interesting to figure out what the complexity must be. There are certainly n additions to perform, and the numbers being added on the k'th step are of size O(phi^k) which will take O(log(phi^k)) = O(k log(phi)) to add. Therefore the total running time is 1 + 2 + ... + n = O(n^2) so the theory predicts quadratic, not linear time. I wonder if this is borne out by numerical experiments.
- leephillips 13y agoI take a small stab at this here: http://lee-phillips.org/lispmath/ http://lee-phillips.org/lispmath/