Constantes escondidas
A notação Big O descarta a constante: O(n) significa "n vezes algum tempo fixo". Quase sempre isso basta, mas às vezes a constante decide quem vence. Imagine uma busca simples que gasta 1 ms por item e uma busca binária que gasta 1 s por passo (porque, por exemplo, cada passo exige uma operação muito mais pesada). Para listas pequenas, a "pior" busca ganha.
Explicação do algoritmo: escolha um nível para ler.
Arraste para os lados para ver o gráfico inteiro.
Por que isso importa
O mesmo raciocínio explica por que o quicksort e a ordenação por mesclagem, ambos O(n log n) em média, não têm o mesmo desempenho na prática: segundo o livro, o quicksort costuma ter uma constante menor e por isso costuma ser mais rápido. Isso depende da implementação e do hardware, então vale medir em vez de supor. Escolher bem o pivô evita o pior caso do quicksort.
A lição do livro: Big O diz como o custo cresce, não quanto tempo leva. Use-o para comparar algoritmos com crescimentos diferentes e, quando o crescimento é o mesmo, olhe também para as constantes.