A sequência de Fibonacci é uma sequência de números inteiros que começa em 1, a que se segue 1, e na qual cada elemento subsequente é a soma dos dois elementos anteriores. A função fib a seguir calcula o n-ésimo elemento da sequência de Fibonacci:

Considerando a implementação acima, avalie as afirmações a seguir.

• I. A complexidade de tempo da função fib é exponencial no valor de n.
• II. A complexidade de espaço da função fib é exponencial no valor de n.
• III. É possível implementar uma versão iterativa da função fib com complexidade de tempo linear no valor de n e complexidade de espaço constante.