#3 es una broma. Es un algoritmo para ordenar listas en tiempo lineal. Usa uno que es un poco peor algoritmicamente hablando (mergesort) y luego espera 1e6 * cada elemento).
Suponiendo que 1e6 fuese un segundo ( que no lo es, sería 1000000) para 2 elementos tardaria 2 segundos, para 3, 3 segundos, y así.
Le resta el tiempo que tarda mergesort para hacerlo exacto.
La broma es que en este caso pese a ser o(n) es muchísimo más lento.
Suponiendo que 1e6 fuese un segundo ( que no lo es, sería 1000000) para 2 elementos tardaria 2 segundos, para 3, 3 segundos, y así.
Le resta el tiempo que tarda mergesort para hacerlo exacto.
La broma es que en este caso pese a ser o(n) es muchísimo más lento.