re: Project Euler #2 - Even Fibonacci numbers VIEW POST


You're correct that addition is O(log N) for a number N, or O(log n) where n is the number of digits. The power function x^n also has a O(log N) time complexity if N is an integer (I presume it's also linear on number of significant bits).

Given fixed sized types on a computer though I believe most of these become constant time, as the inputs have a fixed upper limit on bits. It probably involves an unrolled loop, or fixed iterations on a CPU.

Yes, indeed. I am in fact using just plain double precision numbers there, and they do take a fixed amount of ticks for common operations like those on a modern CPU.

I wouldn't be so certain if I used JavaScript's BigInt numbers (or rather, I would be certain of the opposite).

Thank you for the explanation!

code of conduct - report abuse