Questões de Concurso Público TRF - 5ª REGIÃO 2017 para Analista Judiciário - Informática Desenvolvimento

O algoritmo QuickSort usa uma técnica conhecida por divisão e conquista, onde problemas complexos são reduzidos em problemas menores para se tentar chegar a uma solução. A complexidade média deste algoritmo em sua implementação padrão e a complexidade de pior caso são, respectivamente,

Considere o algoritmo abaixo.

static int fibonacci(int n) { 

   if (n <= 1) { 

      return n; 

   } 

   return fibonacci(n - 2) + fibonacci(n - 1);  

}

A complexidade deste algoritmo, na notação Big O, é