3 ms·
https://en.m.wikipedia.org/wiki/Fibonacci_sequence#Closed-form_expression https://en.m.wikipedia.org/wiki/Fibonacci_sequence#Closed-fo... If exponentiation is
by WolfeReader 2y ago
https://en.m.wikipedia.org/wiki/Fibonacci_sequence#Closed-form_expression https://en.m.wikipedia.org/wiki/Fibonacci_sequence#Closed-fo...
If exponentiation is done using floating-point arithmetic, this is O(1)
- xigoi 2y agoFloats only have a finite precision.
- chowells 2y agoIf you're fine getting wrong answers after the first 73, sure. Some people have higher standards than that.
- xyzzyz 2y agoExponentiation is not a constant time operation, and floating points have finite precision.
- WolfeReader 2y agoExponentiation is constant-time on floats. But as noted by sibling comments, the precision is a problem.
- xyzzyz 2y agoEverything is constant time is your precision is limited. Even the naive, recursive algorithm on integers is constant time if your integer size is limited (it will just be an exponentially big constant). To be able to meaningfully talk about complexity, you need to assume that something is not limited, and once you do that for floats, you’ll find that their exponentiation is no longer constant time.