Encuentre la complejidad computacional
Cuando hablamos del tiempo de ejecución del algoritmo, es convencional dar la función más simple AsymptoticEqual (
grande) para la función de tiempo exacto de ejecución. Otra forma de establecer esta igualdad es que cada función sea tanto AsymptoticLessEqual (
grande) y AsymptoticGreaterEqual (
grande) que la otra. Estos conceptos son ilustrados en el contexto del algoritmo de Strassen, el primer algoritmo de multiplicación de matriz subcúbica encontrado.
El algoritmo consiste en cuatro pasos: dividiendo cada uno de las dos matrices 
en 4 submatrices, formando 14 combinaciones lineales de entre las 8 submatrices, multiplicando 7 pares de estos y sumando los 7 resultados. El tiempo 
para hacer la multiplicación será entonces un tiempo constante 
para dividir la matriz, 
para formar combinaciones lineales en el segundo y cuarto paso y 
para el tercer paso.
Resuelva la relación recurrente.
Aunque el resultado es complicado, 
.
De la misma forma, 
y 
.
Note que 
, así que el algoritmo es subcúbico.
Compare la tasa de crecimiento del algoritmo cúbico ingenuo y el algoritmo de Strassen.
