Carlos Daniel Rodriguez
PreguntaPor qué MERGE SORT es de complejidad “n Log n”?, si habíamos visto que la recursividad multiple (como en fibonacci) era “Exponencial” 2^n
CRISTIAN BARBERO PÉREZ
La clave está en que es un algoritmo divide y vencerás. Al dividir en 2 el array en cada iteración estás limitando esta recursividad.
Es decir, si tienes un array inicial de longitud 16, tendrás que dividirlo 3 veces, pero si aumentas la longitud a 32 tendrás que dividirlo solamente 4. Y si aumenta a 64 solamente 5. Esto es un crecimiento logarítmico.
Me gusta bastante la segunda respuesta que dan aquí.
En cambio en fibonacci por cada elemento que añadas al array estarás añadiendo el doble de operaciones. Si quieres calcular fibonacci(3) harás dos operaciones, para fibonacci(4) cuatro operaciones, para fibonacci(5) ya ocho operaciones
