Complexidade de Algoritmo: O número de comparações de um algoritmo de ordenação é
. Para quais valores de
o número de comparações é exatamente 90 ?
Passo 1
O enunciado dá a fórmula do número de comparações de um algoritmo de ordenação:
. Pede-se encontrar os valores de
para os quais o número de comparações é exatamente
.
Informações relevantes fornecidas:
- A função que dá o número de comparações é
. - Queremos
. - Implicação prática:
é o número de elementos a ordenar, portanto deve ser um número inteiro e não-negativo (normalmente ).
Passo 2
Escrevendo a equação que precisamos resolver:
Subtraindo
de ambos os lados para obter uma equação quadrática padrão:
Uma equação quadrática tem a forma geral
. Aqui temos
,
e
.
Passo 3
Método 1 — fatoração: procurar dois números cujo produto seja
e cuja soma seja
. Esses números são
e
, porque
e
. Assim a quadrática fatoriza como
Para que o produto seja zero, um dos fatores deve ser zero, portanto as soluções são
isto é,
ou
.
Passo 4
Método 2 — fórmula de Bhaskara (verificação/recapitulando a técnica): para a equação
a solução é
Aqui
,
,
. O discriminante é
e
. Assim
o que dá
ou
, coincidente com a fatoração.
Passo 5
Aplicando a restrição prática:
representa número de elementos, logo deve ser inteiro não-negativo. Das duas soluções encontradas,
é negativa e não faz sentido no contexto, então é descartada. Verificação direta da solução admissível:
logo
funciona corretamente.