¿Cuántas iteraciones hay, si cada iteración resuelve el log m del m restante? Educación te da un futuro mejor

Trabajemos al revés, y asumamos la base de registro 2. El algoritmo termina cuando queda 1 elemento ([matemática] m = 1, \ log_2 (m) = 0 [/ matemática]). Suponiendo que acabamos de llegar allí, el paso anterior debe tener [matemática] m = 2 [/ matemática], porque [matemática] \ log_2 (2) = 1 [/ matemática] y [matemática] 2 – 1 = 1 [/ matemática] . El paso anterior debe tener [math] m = 4 [/ math], porque [math] \ log_2 (4) = 2 [/ math] y [math] 4 – 2 = 2 [/ math]. Puede comenzar a sospechar que [matemática] m [/ matemática] aumenta exponencialmente como [matemática] 2 ^ k [/ matemática], pero eso no es cierto porque 8 eliminaría 3 elementos, dejando 5 no 4. Entonces el siguiente número es un número entero menor que 7. De hecho, si observa un [matemático] m [/ matemático] muy grande como [matemático] 2 ^ {100} [/ matemático] (en adelante), solo sacará 100 , y el número resultante seguirá siendo muy cercano a [math] 2 ^ {100} [/ math], por lo que sacará casi 100 durante mucho tiempo. Por lo tanto, para números grandes, el tiempo de ejecución será algo así como [matemática] O (\ frac {m} {\ log (m)}) [/ matemática]. (Para la notación grande [matemática] O () [/ matemática], la base no importa).

Para el registro natural, podemos ver este comportamiento para [matemática] n [/ matemática] igual a varias potencias de 10 (usando coma flotante y terminando cuando [matemática] m <1.5 [/ matemática]):

10 ^ 0 toma 0 pasos
10 ^ 1 toma 6 pasos (0.6 * n)
10 ^ 2 toma 29 pasos (0.29 * n)
10 ^ 3 toma 177 pasos (0.177 * n)
10 ^ 4 toma 1245 pasos (0.1245 * n)
10 ^ 5 toma 9629 pasos (0.09629 * n)
10 ^ 6 toma 78626 pasos (0.078626 * n)
10 ^ 7 toma 664917 pasos (0.0664917 * n)
10 ^ 8 toma 5762208 pasos (0.05762208 * n)
10 ^ 9 toma 50849233 pasos (0.050849233 * n)
10 ^ 10 toma 455055613 pasos (0.0455055613 * n)

Entonces es sublineal, pero no por mucho.