Big O complexity of the basic arithmetic operations
algorithm, big-o, complexity-theory, math, time-complexity
Solution
See http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations
Matrix product of square matrices:
- O(N3) (naïve method)
- O(N2.81) (Strassen's algorithm).
There is also a O(N2.38) Coppersmith–Winograd algorithm but I don't think it's wide-spread due to the huge hidden constant.
Big-int multiplication:
- Naïve: O(n2)
- Fast-Fourier transform based: O(n log n log log n) (Schönhage–Strassen algorithm).
There are also an n log n · 2O(log* n) algorithm published in 2008 but that was too new to be widespread.
Usually the naïve method is good enough for normal-sized input.
Problem
What is the Big-O complexity for widespread algorithms of the basic arithmetic operations like multiplication, square root, logarithm, scalar and matrix product? Are there exotic algorithms which are more efficient, in terms of Big-O complexity, but are not very widespread in practical solutions (e.g. not implemented in popular software libraries)?