O algoritmo O(log n) costuma ter problema de localidade de referência então o O(n) acaba sendo mais rápido em muitos casos. Olhando um outro aspecto um O(1) pode ser mais lento em alguns casos que um O(log n) ou mesmo complexidades maiores como O(n).
De modo que o tempo de execução de um algoritmo pode ser dado como uma função T(n) do tamanho n da sua entrada. Por exemplo, um programa pode ter tempo de execução T(n) = n2 + n + 1. A unidade de T(n) é em principio instrução executada.
Função clock() e a macro CLOCKS_PER_SEC Para encontrar o tempo de execução de um programa precisamos usar ela duas vezes, uma para capturar o tempo inicial e outra para capturar o tempo final da execução. Se fizermos o tempo final - tempo inicial teremos o tempo de execução do programa em milissegundos.
Notação O: Usada para análise de pior caso de algoritmos, Também chamado limite superior. “T(n) é O(f(n))” deve ser entendido como “T(n) ∈ O(f(n))”. “T(n) = O(f(n))” deve ser entendido como “T(n) ∈ O(f(n))”. n0 Usada para análise de melhor caso ou estabelecer complexidade de problemas.
De uma maneira simplificada e mais objetiva possível, o comportamento assintótico pode ser entendido como a curva de crescimento da função gerada pelo processo de análise de algoritmos. ... Por exemplo: o algoritmo de ordenação Bubble Sort (no pior caso) possui complexidade T(n)=5n2-n+1.
Assim, log n é uma abreviatura de log2 n , ou seja, o número real x tal que 2 x = n . ... Portanto, log n é essencialmente igual ao número de dígitos na representação binária de n , ou, equivalentemente, cerca de 3.
Tabela de logaritmos decimais
Exemplo numérico: log81 = 0, pois 80 = 1. logbb = 1, pois b1 = b.
Assim, o logaritmo de "50" terá uma característica "1", pois "50" tem dois algarismos e "2-1 = 1", enquanto a característica se mantém a mesma vista para o logaritmo de "5". Logo, teríamos para o logaritmo de "50", aproximadamente: log₁₀ (50) = 1,69897