Complexidade de Algoritmo: O número de comparações de um algoritmo de ordenação é C(n)=n^{2}-n. Para quais valores de n 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: C(n)=n^{2}-n. Pede-se encontrar os valores de n para os quais o número de comparações é exatamente 90.
Informações relevantes fornecidas:
  • A função que dá o número de comparações é C(n)=n^{2}-n.
  • Queremos C(n)=90.
  • Implicação prática: n é o número de elementos a ordenar, portanto deve ser um número inteiro e não-negativo (normalmente n\in\{0,1,2,\dots\}).

Passo 2

Escrevendo a equação que precisamos resolver:
n^{2}-n=90.
Subtraindo 90 de ambos os lados para obter uma equação quadrática padrão:
n^{2}-n-90=0.
Uma equação quadrática tem a forma geral ax^{2}+bx+c=0. Aqui temos a=1, b=-1 e c=-90.

Passo 3

Método 1 — fatoração: procurar dois números cujo produto seja c=-90 e cuja soma seja b=-1. Esses números são -10 e 9, porque (-10)\cdot 9=-90 e (-10)+9=-1. Assim a quadrática fatoriza como
n^{2}-n-90=(n-10)(n+9).
Para que o produto seja zero, um dos fatores deve ser zero, portanto as soluções são
n-10=0\quad\text{ou}\quad n+9=0,
isto é, n=10 ou n=-9.

Passo 4

Método 2 — fórmula de Bhaskara (verificação/recapitulando a técnica): para a equação an^{2}+bn+c=0 a solução é
n=\frac{-b\pm\sqrt{b^{2}-4ac}}{2a}.
Aqui a=1, b=-1, c=-90. O discriminante é
\Delta=b^{2}-4ac = (-1)^{2}-4\cdot1\cdot(-90)=1+360=361,
e \sqrt{\Delta}=\sqrt{361}=19. Assim
n=\frac{-(-1)\pm19}{2\cdot1}=\frac{1\pm19}{2},
o que dá n=\dfrac{1+19}{2}=10 ou n=\dfrac{1-19}{2}=-9, coincidente com a fatoração.

Passo 5

Aplicando a restrição prática: n representa número de elementos, logo deve ser inteiro não-negativo. Das duas soluções encontradas, n=-9 é negativa e não faz sentido no contexto, então é descartada. Verificação direta da solução admissível:
C(10)=10^{2}-10=100-10=90,
logo n=10 funciona corretamente.

Resposta

n=10

Exercícios relacionados