3 ms·
there's a reasonable expectation that a repo named "cool algorithms" won't use extremely dumb exponential-time versions when linear-time ones exist. Also in thi
by xdavidliu 4y ago
there's a reasonable expectation that a repo named "cool algorithms" won't use extremely dumb exponential-time versions when linear-time ones exist. Also in this case there's a logarithmic-time one that does repeated squaring of a 2x2 matrix.
- im3w1l 4y agoArithmetic on bignums is not O(1), but rather depends on the size of the numbers. This is important when considering say the repeated matrix squaring vs an evaluation of the closed form. They both beat naive exponential time algos, of course.