Re:Big-O Algorithm Complexity Cheat Sheet
by eru on Sunday May 05, 2013 @03:16AM
(#5657695)
> For that matter, multiplication is not constant time either - it's O(N) in the number of bits [...]
Actually, multiplication is worth than O(bits). A naive approach will yield O(bits^2), but you can get something like O(bits^r) where r is not too much bigger than 1. See https://en.wikipedia.org/wiki/Multiplication_algorithm#Fast_... for an introduction
Actually, multiplication is worth than O(bits). A naive approach will yield O(bits^2), but you can get something like O(bits^r) where r is not too much bigger than 1. See https://en.wikipedia.org/wiki/Multiplication_algorithm#Fast_... for an introduction