¿Cuál es la complejidad temporal indicada del algoritmo recursivo ingenuo de Fibonacci?

O(2ⁿ)

La complejidad temporal de el procedimiento descrito es O(2ⁿ). En matemáticas, la sucesión de Fibonacci es: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … {\displaystyle 0,1,1,2,3,5,8,13,21,34,55. La notación O grande describe cómo crece el trabajo necesario cuando aumenta el tamaño de la entrada.

O(2ⁿ) no representa un número fijo de segundos: expresa una tendencia de crecimiento y permite comparar algoritmos sin depender de un ordenador concreto. Factores constantes y detalles de implementación pueden afectar al tiempo real, pero la clase O(2ⁿ) resume el comportamiento dominante para entradas grandes. La conexión de «O(2ⁿ)» con la tecnología ofrece una referencia clara para conservar la información. El contexto que rodea «O(2ⁿ)» dentro de la tecnología permite reconocer por qué es aquí el dato relevante.