Comparando ordens de grandeza

  versus  

O número de passos em uma busca sequencial de uma lista ordenada é  , e em uma busca binária é  . O que significa esta afirmação? Vamos aos fatos:

1) Definição: Sejam f(x) e g(x) funções positivas para x suficientemente grande. Dizemos que, f é no máximo da ordem de g para x suficientemente grande, se existe inteiro M >0, tal que

para estes x, isto é, a função f é envelopada pela função Mg.

2) A ordem de grandeza é importante na análise de um algoritmo computacional, onde o número de vezes de uma tarefa é executada depende do tamanho dos dados de entrada. Para entender melhor o efeito da ordem de graneza na análise de algoritmos, suponha dois algoritmos,  e  fazendo a mesma coisa, mas   é    e    é . Para processar dados de entrada de tamanho 100, n = 100,  processa em 0,01 segundos e  em 1 segundo e, essa diferença afeta sensivelmente o tempo de computação à medida que n vai ficando maior.

3) Conclusão: É importante colocar o algoritmo em funcionamento, procurar saber se existe um outro algoritmo que faça o mesmo efeito, com ordem de grandeza menor.