<code>fibonacci_dinamico</code> y fibonacci_recursivo tiene la misma complejidad logarítmica?

Cuando implementamos el Fibonacci dinámico bajamos el nivel de complejidad de O(2**n) a O(n), aunque en este caso funciona muy bien, hay que tener en cuenta que se hizo un "trade-off" ya que por otro lado aumentamos la complejidad en espacio que paso de ser constante a O(n). Esto se debe a que ahora requiero espacio adicional (el diccionario) que incrementa según el n que quiera calcular.

La diferencia entre ambos algoritmos es que el

La complejidad del recursivo es casi O(2^n) (de hecho en vez de dos exactamente es el número de oro :O) debido a que hay que hacer los cálculos una y otra vez.

Mientras que la complejidad del dinámico es O(n), debido a que solo hay que hacer los cálculos una vez y estos se van almacenando.

La forma más fácil de notarlo es hacerlo a mano, pero si te interesa un poco más el tema y quieres ver una respuesta más rigurosa haz click aquí.