Transformation Methods Complexity Concerns One of the interesting morals from theoretical computer science is that many familiar algorithms are far from optimal. In order to be more precise we introduce the notion of bit complexity . Bit complexity counts the number of single operations required to complete an algorithm. This is a good measure of time on a serial machine. Thus, addition of two n -digit integers by the usual method has bit complexity , straightforward uniqueness considerations show this to be asymptotically best possible.
Multiplication is a different story.
Usual multiplication of two n -digit integers has bit complexity and no better. However, it is possible to multiply two n -digit integers with complexity . It provides the best bound known for multiplication. No multiplication can have speed better than . Unhappily, more exact results aren't available.