5 ms·
A similar neat O(log(n)) solution https://kukuruku.co/post/the-nth-fibonacci-number-in-olog-n/ https://kukuruku.co/post/the-nth-fibonacci-number-in-olog-n/
by maksimum 7y ago
A similar neat O(log(n)) solution https://kukuruku.co/post/the-nth-fibonacci-number-in-olog-n/ https://kukuruku.co/post/the-nth-fibonacci-number-in-olog-n/
- bingerman 7y agoThe first chapter of SICP also has a similar (but not identical) O(log(n)) algorithm in the excercises. Fun stuff.
- SmartestUnknown 7y agon^th Fibonacci number requires O(n) bits. So, saying the solution is O(log(n)) is kinda not true. I mean there cannot be a o(n) algorithm for computing decimal representation of n^th fibonacci number.
- kadoban 7y agoAs always, it depends on your computational model. People are awful at specifying a model, in other words it's unclear what's even being stated. You can compute the nth fibonacci number in O(lg n) additions and multiplies. That indeed doesn't turn out to be a good model for how long it takes on an actual computer though.
- madez 7y agoAnd even if the model is sufficiently specified, the constant factors and lower terms hidden in the O-notationen can be deciding in practice, and are yet usually left out.