Efficacité de l'algorithme

Si la matrice possède L lignes et C colonnes, le nombre maximal d'opérations pour réduire une ligne est C divisions, C multiplications, C soustractions, donc 3C opérations arithmétiques de base. Il y a L - 1 lignes à réduire à chaque étape et min(L, C) étapes à effectuer, on en déduit que le nombre maximal d'opérations pour réduire une matrice est 3LCmin(L, C). Pour une matrice carrée de taille n, cela fait 3n³ opérations.