O (log n) é sempre mais rápido que o (n)?

Acredito que a pergunta está incorreta e que você deseja perguntar: "Um algoritmo O (log n) é sempre mais rápido que um algoritmo O (n)?"

A resposta é não, por várias razões:

  • A expressão O (f (n)) significa que o tempo de execução é no máximo C f (n) com C uma constante cujo valor é deixado indefinido. É bem possível que a constante para O (log n) seja muito maior que a constante para O (n). E, portanto, é possível que O (log n) seja mais rápido que O (n) apenas para n maior que 1 milhão, que podem ser valores que ninguém usa.
  • Qual é exatamente o significado de O (f (n))? É uma complexidade de pior caso, uma complexidade média de caso? Às vezes, algum algoritmo primitivo pode ter um desempenho muito bom em todos os casos de interesse e, portanto, ser totalmente aceitável.
  • O (f (n)) significa apenas que a corrida é no máximo C f (n). Mas talvez a análise do algoritmo não tenha sido feita suficientemente bem e, na verdade, seja menor do que isso. Se o tempo de execução é no máximo C f (n) e pelo menos C 'f (n), então escrevemos \ Omega (f (n)).

Então, como você vê, tudo pode ser qualificado.