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. É correto o que se afirma em