Fundamentos e teoria da computação

Oi, Carlos!

Considerando que nosso algoritmo é , para resolver um problema com tamanho , serão necessárias  operações, independentemente do computador.

Agora, pense que, se a velocidade de nosso computador é , onde

, ou seja, é o número de operações  que o computador executa em um intervalo de tempo

Assim, para o computador antigo, temos

Para o novo computador, temos

Sabemos, então, que podemos executar  operações  no mesmo intervalo de tempo.

Como , temos que .

Assim, apesar de termos um computador novo 100 vezes mais rápido, podemos resolver o mesmo problema com entradas apenas 10 vezes maior (o que é condizente com a ordem quadrática do algoritmo)

A quantidade de instruções executadas em tempo 't' é de 25, isso quer dizer que a quantidade de instruções executadas é de 2*(25)² = 1,250 instruções. Já no novo computador 100 vezes mais rápido, temos, 100*2n². Portanto, 100*2*(25)² = 125,000.

O computador novo consegue resolver 100 vezes mais instruções.

:)