(Questão 05-06 pontos)
Para o método de ordenação Quicksort o seu pior caso ocorre quando cada partição divide o arquivo em uma parte de tamanho
e outra parte de tamanho 1 .
Em contrapartida, o melhor caso ocorre quando cada partição divide o arquivo em duas partes iguais.
Mostre, a partir da resolução das equações de recorrência, qual a ordem de complexidade para cada um dos casos.
Passo 1
O enunciado trata do Quicksort e dá duas recorrências: no pior caso
e no melhor caso
Vamos resolver cada uma para determinar a ordem de crescimento.
Passo 2
Para o pior caso, use expansão (ou somatório). Suponha
. Expandindo até
:
Como
concluímos
Passo 3
Para o melhor caso, aplicamos o Teorema Mestre à recorrência
Aqui
,
e
. Como
e
, estamos no caso 2 do Mestre, que dá
Resposta
Pior caso:
Melhor caso:
Melhor caso: