La escritura de un entero A en base N se parece a la de un polinomio:
A = a + bN + cN 2 +… donde a, b, c… son números enteros comprendidos entre 0 y N – 1. Para sumar dos números de n cifras mediante el algoritmo clásico, enseñado en primaria, se realizan n sumas de números de una cifra y, si es necesario, n sumas correspondientes a los acarreos. Al usar un ordenador se comprueba que, para números muy grandes, el tiempo de cálculo es proporcional a n. Más precisamente, está acotado superiormente por una constante multiplicada por n, lo que se denota O(n) («O grande de n»). Se dice que su complejidad —un modelo matemático del tiempo de cálculo— es lineal.
Con el algoritmo clásico, enseñado en las escuelas, la multiplicación no es lineal, sino cuadrática: su complejidad es O(n2), pues se realizan n 2 multiplicaciones de números de una cifra y después unas n sumas. Al usar un ordenador se comprueba que el tiempo de cálculo para números grandes es proporcional a n 2.
Los ordenadores se han vuelto tan potentes que estas mediciones solo se hacen visibles con números de varios miles de cifras. Pero, si se duplica el número de cifras, el tiempo de cálculo se multiplica por 4. En el caso de la suma, el tiempo de cálculo solo se duplica; ahí radica toda la diferencia entre complejidad lineal y complejidad cuadrática.
El algoritmo de Strassen ============================