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!
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
You're correct that addition is
O(log N)for a number N, orO(log n)where n is the number of digits. The power functionx^nalso has aO(log N)time complexity ifNis 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!