<!DOCTYPE html>
<html lang="pt-BR">
<head>
 <meta charset="UTF-8">
 <style>
 body {
 font-size: 16px;
 line-height: 1.5;
 }
 .blue {
 color: blue;
 }
 math {
 font-size: 16px;
 }
 </style>
</head>
<body>
A compreensão da complexidade de um algoritmo é fundamental para analisar sua eficiência em termos de tempo de execução conforme o tamanho da entrada cresce. O QuickSort é um exemplo clássico de algoritmo que emprega a estratégia de divisão e conquista, particionando o array e recursivamente ordenando as partições.
 
A complexidade média do QuickSort, em sua forma mais comum, é:
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block" style="font-size: 16px;">
 <mi>O</mi>
 <mo>(</mo>
 <mi>n</mi>
 <mi>⁡</mi>
 <mi>log</mi>
 <mi>n</mi>
 <mo>)</mo>
</math>
 
Essa complexidade é obtida porque, em média, o pivô divide o array em duas partes iguais, levando a uma profundidade logarítmica de recursão, e cada nível de recursão envolve um trabalho proporcional a n para a particionamento.
 
Por outro lado, a complexidade de pior caso do QuickSort ocorre quando o pivô divide o array de modo desbalanceado, levando a um cenário onde cada chamada recursiva tem apenas um elemento a menos que a chamada anterior, configurando assim uma complexidade:
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block" style="font-size: 16px;">
 <mi>O</mi>
 <mo>(</mo>
 <msup>
 <mi>n</mi>
 <mn>2</mn>
 </msup>
 <mo>)</mo>
</math>
 
Analisando cada alternativa dada na questão:
<ul>
 <li>A) O(n-1) e Ο(n³):
 Incorreta. A expressão O(n-1) não é uma representação padrão de complexidade, e Ο(n³) é extraordinariamente pessimista e não corresponde ao reconhecido pior caso do QuickSort.
 </li>
 
 <li>B) Ο(n²) e Ο(n log n²):
 Incorreta. Embora Ο(n²) possa descrever o pior caso, Ο(n log n²) não é uma representação típica para o pior caso ou caso médio do QuickSort.
 </li>
 
 <li>C) O(n²) e O(n³):
 Incorreta. A alternativa repete o erro sobre o pior caso sendo O(n³), que é também incorreta ao lado de O(n²) para o pior cenário.
 </li>
 
 <li>D) Ο(n) e Ο(n²):
 Incorreta. Ο(n) não reflete precisamente nenhuma situação usual do QuickSort - nem média nem pior caso.
 </li>
 
 <li>E) Ο(n log n) e Ο(n²):
 Correta. Reflete adequadamente a complexidade média e a complexidade de pior caso do QuickSort, respectivamente.
 </li>
 
</ul>
 
Portanto, a alternativa correta é E.
 

</body>
</html>

<!DOCTYPE html>
<html lang="pt-BR">
<head>
 <meta charset="UTF-8">
 <style>
 body {
 font-size: 16px;
 line-height: 1.5;
 }
 .blue {
 color: blue;
 }
 math {
 font-size: 16px;
 }
 </style>
</head>
<body>
 A função <code>fibonacci</code> apresentada demonstra um algoritmo recursivo clássico para calcular o n-ésimo número da sequência de Fibonacci. Este algoritmo tem uma característica distintiva: a função é chamada duas vezes dentro de sua definição, cada chamada com um decremento diferente (n-2, n-1).
 

 Para analisar a complexidade de tempo do algoritmo acima, é importante reconhecer que cada chamada à função <code>fibonacci</code> gera duas novas chamadas até o caso base ser alcançado (n <= 1). A repetição dessa bifurcação resulta em uma árvore de chamadas recursivas, onde o número de chamadas cresce exponencialmente com o aumento de n.
 

 A complexidade dessa função pode ser descrita por uma relação de recorrência:
 <math xmlns="http://www.w3.org/1998/Math/MathML" display="block" style="font-size: 16px;">
 <mi>T</mi>
 <mo>(</mo>
 <mi>n</mi>
 <mo>)</mo>
 <mo>=</mo>
 <mi>T</mi>
 <mo>(</mo>
 <mi>n</mi>
 <mo>-</mo>
 <mn>1</mn>
 <mo>)</mo>
 <mo>+</mo>
 <mi>T</mi>
 <mo>(</mo>
 <mi>n</mi>
 <mo>-</mo>
 <mn>2</mn>
 <mo>)</mo>
 <mo>+</mo>
 <mi>O</mi>
 <mo>(</mo>
 <mn>1</mn>
 <mo>)</mo>
 </math>
 
 

 Essencialmente, a árvore de recursão cresce geometricamente, e pode-se visualizar isso como o dobro das chamadas a cada nível de recursão. Portanto, após n-itens, o número total de chamadas é proporcional a 2n. Isso coloca a função no contexto da complexidade O(2n).
 

 Analisando cada alternativa dada:
 
 <ul>
 <li>A) O(2n):
 Correto, pois descreve a complexidade exponencial do algoritmo, como evidenciado pela duplicação do número de chamadas a cada novo nível de recursão.
 </li>
 
 <li>B) O(n2):
 Incorreto, pois essa seria a complexidade de algoritmos com crescimento quadrático, não exponencial.
 </li>
 
 <li>C) O(n):
 Incorreto, pois essa notação descreve uma complexidade linear, o que não se aplica ao caso de bifurcação recursiva.
 </li>
 
 <li>D) O(log(n)):
 Incorreto, descreve algoritmos que dividem o problema em partes menores a cada etapa, geralmente associados a pesquisas eficientes, como busca binária.
 </li>
 
 <li>E) O(n4):
 Incorreto, descreve uma complexidade ainda mais elevada e não reflete o crescimento da árvore de recursão do algoritmo Fibonacci.
 </li>
 
 </ul>
 

 Portanto, a alternativa correta é A.
 

</body>
</html>

Questões de Tecnologia da Informação - Complexidade de algoritmos - Tribunal Regional Federal 5ª Região