Sea una matriz cuadrada de orden . El algoritmo clásico de multiplicación por un vector tiene la misma complejidad computacional que la multiplicación de la matriz por un escalar.

Para matrices , el algoritmo clásico de multiplicación de matrices tiene complejidad , aunque hay casos en los que se puede reducir a .

Leer las entradas de una matriz almacenada en memoria tiene una complejidad computacional diferente si se recorre la matriz fila a fila o si se recorre columna a columna.

Para un problema particular, un algoritmo de complejidad puede requerir menos operaciones que otro de complejidad .