Tempo de execução de algoritmos

Para determinar o menor valor de n para o qual o algoritmo de tempo de execução 100n² é mais rápido do que o algoritmo de tempo de execução 2n, podemos igualar as expressões e resolver para n.

Isto é, 100n² = 2n.

Dividindo ambos os lados da equação por n, obtemos:

100n = 2

n = 2 / 100

n = 0,02

Portanto, o menor valor de n para o qual o algoritmo de tempo de execução 100n² é mais rápido do que o algoritmo de tempo de execução 2n é n = 0,02. Para valores de n menores que 0,02, o algoritmo de tempo de execução 2n seria mais rápido, enquanto para valores de n maiores que 0,02, o algoritmo de tempo de execução 100n² seria mais rápido.

Para determinar o menor valor de nn onde o algoritmo com tempo de execução 100n2100n^2 é mais rápido que o algoritmo com tempo de execução 2n2^n, devemos resolver a inequação:

100n2<2n100n^2 < 2^n

Passo 1: Tentar valores pequenos de nn manualmente

Para valores pequenos de nn, podemos testar diretamente:

Observe que 100n2>2n100n^2 > 2^n para valores pequenos de nn.

Passo 2: Verificar quando 100n2<2n100n^2 < 2^n

Os valores crescem exponencialmente para 2n2^n, então é esperado que a partir de algum ponto nn, 2n2^n ultrapasse 100n2100n^2.

Usando cálculo: Para resolver aproximadamente, tomamos logaritmos de ambos os lados:

log?(100n2)<log?(2n)\log(100n^2) < \log(2^n)

Expandindo:

log?(100)+2log?(n)<nlog?(2)\log(100) + 2\log(n) < n\log(2)

Aproximação:

1. Sabemos que log?(100)=2\log(100) = 2, e log?(2)?0.301\log(2) \approx 0.301.
2. Para nn, podemos iterar numericamente ou graficamente para encontrar a solução.

Resultado Aproximado

• Para n=15n = 15, 100n2=22500100n^2 = 22500 e 2n=327682^n = 32768.
• Para n=14n = 14, 100n2=19600100n^2 = 19600 e 2n=163842^n = 16384.

Portanto, o menor valor de nn tal que 100n2<2n100n^2 < 2^n é:

n=15n = 15