Hola. ¿Por qué el Big O de la función de Fibonacci es 2**n? No me quedó muy claro, gracias.

Porque cada que ejecutras la función vas a invocar dos funciones(la misma)

Haré un intento: La base 2 es debido a que en la función esta se llama recursivamente dos veces así misma. Como ves en la imagen que comparte @Cristian se bifurca dos veces en cada iteracación. Y bueno n es el parámetro de la serie.

¡Éxitos!

Buenas compañero, creo que con esta imagen se ve muy bien:

Si te das cuenta cada rama se divide en 2, es decir, el número de ramas se multiplica por dos en cada iteración, por eso es de la forma 2**n.