Até agora, analisamos a busca linear e a busca binária contando o número máximo de tentativas necessárias. Mas o que realmente queremos saber é quanto tempo esses algoritmos demoram. Estamos interessados no tempo, não só nas suposições. Os tempos de execução da busca linear e da busca binária incluem o tempo necessário para gerar e checar palpites, mas algoritmos não se resumem a isso.
O tempo de execução de um algoritmo depende do quão demorado é para um computador executar as linhas de código do algoritmo e isto depende da velocidade deste computador, da linguagem de programação, e do compilador que traduziu o programa da linguagem de programação para o código que executa diretamente no computador, entre outros fatores.
Vamos pensar com mais cuidado no tempo de execução de um algoritmo. Podemos usar a combinação de duas ideias. Primeiro, precisamos determinar quanto tempo o algoritmo leva em termos do tamanho da entrada. Esta ideia parece intuitiva, não é mesmo? Já vimos que o máximo de tentativas necessárias em busca linear e em busca binária aumenta conforme aumenta o tamanho do array de candidatos. Ou pense sobre um GPS. Se ele conhecesse apenas o sistema de rodovias principais, e não todas as pequenas estradas secundárias, ele deveria ser capaz de buscar rotas mais rapidamente, certo? So we think about the running time of the algorithm as a function of the size of its input.
A segunda ideia é que precisamos focar em quão rápido uma função cresce com o tamanho da entrada. Chamamos isso de taxa de crescimento do tempo de execução. Para manter as coisas tratáveis, precisamos simplificar a função até evidenciar a parte mais importante e deixar de lado as menos importantes. Por exemplo, suponha que um algoritmo, sendo executado com uma entrada de tamanho n n , leve 6n2+100n+300 6n^2 + 100n + 300 instruções de máquina. O termo 6n2 6n^2 torna-se maior do que os outros termos, 100n+300 100n + 300 , uma vez que n n torna-se grande o suficiente,  20  neste caso. Abaixo temos um gráfico que mostra os valores de 6n2 6n^2 e 100n+300 100n + 300 para valores de n n variando entre 0 e 100:
Podemos dizer que este algoritmo cresce a uma taxa n2 n^2 , deixando de fora o coeficiente 6 e os termos restantes 100n+300 100n + 300 . Não é realmente importante que coeficientes usamos, já que o tempo de execução é an2+bn+c an^2 + bn + c , para alguns números a>0 a > 0 , b b , e c c , sempre haverá um valor de n n para o qual an2 an^2 é maior que bn+c bn + c , e essa diferença aumenta juntamente com n n . Por exemplo, aqui está um gráfico mostrando os valores de 0,6n2 0{,}6n^2 e 1000n+3000 1000n + 3000   de modo que reduzimos o coeficiente de n2 n^2 por um fator de 10 e aumentamos as outras duas constantes por um fator de 10:
O valor de n n para o qual 0,6n2 0,6n^2 se torna maior que 1000n+3000 1000n + 3000 aumentou, mas sempre haverá um ponto de cruzamento, independentemente das constantes.
Descartando os termos menos significativos e os coeficientes constantes, podemos nos concentrar na parte importante do tempo de execução de um algoritmo — sua taxa de crescimento — sem sermos atrapalhados por detalhes que complicam sua compreensão. Quando descartamos os coeficientes constantes e os termos menos significativos, usamos notação assintótica. Vamos estudar suas três formas: notação Θ \Theta , notação O, notação Ω \Omega .

Este conteúdo é uma colaboração entre os professores Thomas Cormen e Devin Balkcom da Dartmouth Computer Science e a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.
Carregando