Ya se ha visto cómo el tiempo de ejecución del algoritmo de Arcadio crece aproximadamente 2n con el tamaño de la entrada n. A una relación como ésta, en general se le denomina función exponencial f (n): la variable independiente, la n, forma parte del exponente al que se eleva algún número, en este caso el 2. Por ejemplo, al multiplicar el 3 por sí mismo n veces, se obtiene otra función exponencial, f (n) = 3n.
El tiempo para resolver un problema crece de manera exponencial cuando, como en el caso de Arcadio, hay que buscar una solución en un conjunto muy grande, cuyo tamaño es exponencial. Si la entrada es de tamaño n, el conjunto sería de tamaño f (n). Y más aún, no existen pistas que guíen la búsqueda, que eviten revisar, una por una, todas las opciones que surgen para determinar cuál es la óptima. Se enfrenta un problema complejo en el sentido computacional del término, cuya solución requiere de mucho, muchísimo tiempo, aun cuando el tamaño de la entrada no sea muy grande. Para entender esto, la información de la tabla 4 puede ser de gran utilidad, ya que representa el tiempo de ejecución del algoritmo de Arcadio. Supóngase que emplea 10 segundos en escribir cada fila. En la tabla se observa que considerar 20 regalos implica demasiado tiempo, puesto que se necesitarían más de 121 días; no se diga considerar 30 regalos, ¡llevaría más de 340 años completar la tabla!
Ante el crecimiento exponencial, de poco sirve la tecnología. Puesto que el amor de Arcadio es enorme y no está dispuesto a tomar una decisión sin considerar al menos 20 posibles regalos, pero esperar 121 días está fuera de cuestión (pues para entonces Úrsula ya habría regresado con su ex novio), decide contratar a un programador que ejecute su algoritmo en una veloz computadora e imagina que será una herramienta útil para calcular cada fila de la tabla miles de veces más rápido que él; tal vez, un millón de veces más rápido que él. Es decir, en lugar de 10 segundos, 10/1 000 000 segundos = 10 μs. Dado que 220 = 1 048 576, para calcular el tiempo, habría que multiplicar este número por 10 microsegundos; de este modo todo se reduce a únicamente 10.48576 segundos. "Perfecto", piensa Arcadio.
Sólo que ahora decide que la belleza de Úrsula es aún mayor y que por lo menos debe considerar 30 regalos. Con esto el tiempo empleado se eleva a 10 073 741 824 segundos, o sea, 2.77 horas de ejecución en una veloz computadora. "Mmm…", reflexiona Arcadio, "¿será muy caro rentar la computadora por un poco más de tiempo y considerar por lo menos 35 regalos?" Arcadio realmente ama a Úrsula. El tiempo se dispara a más de 164 horas, es decir, 6.8 días; y para el cálculo de 40 regalos se emplearían años de ejecución en una veloz computadora.
Curiosidades
Si a alguien le ofrecen un átomo de oro por cada segundo transcurrido desde el Big Bang, ¿se haría rico? Resulta que los átomos son tan increíblemente pequeños, que esa cantidad de átomos equivale solamente al pedacito de una moneda de oro que pesa 0.14 miligramos y no vale más que unos cuantos pesos.
