No obstante, la velocidad de ejecución de ambos formalismos no es la misma, pues si una máquina no determinista "M" reconoce una cierta palabra de tamaño "n" en un tiempo formula_44, la máquina determinista equivalente reconocerá la palabra en un tiempo formula_45.