[Desenvolvimento] O(log n) é bom, mas por quê?

 Todo mundo já está mais que ligado nesse graficozinho do nosso querido Big O:

A gente também já sabe que N é o número de itens ou iterações que um algoritmo utiliza, mas qualé do “log”, lembra quando eu sempre falo que matemática é sim um divisor de águas em programação, pois é, esse “log” é logaritmo, e isso amigão, é matemática (como tudo em desenvolvimento).

“Em matemática, logaritmo é a operação inversa da exponenciação. Ou seja, chamamos de logaritmo de um número o expoente a que outro valor (a base) deve ser elevado para produzir este número.”

Vamos tentar simplificar, pensando mais no contexto de desenvolvimento, focando em complexidade de algoritmo. Primeiro, vamos supor que a base sempre seja 2, para deixar as coisas mais fáceis.

Então se O(1) é constante e O(n) é linear, O(log n) é basicamente: 2 ^x = N ou seja, sempre que N dobrar seu tamanho, X irá aumentar um, bora ver uns exemplos:

log(4) = 2     -     log(8) = 3     -     log(16) = 4     -     log(32) = 5     -     log(64) = 6

Podemos ver que quanto maior for N, menor serão as alterações na nossa performance.

Então, pensando em como nossa maravilhosa Binary Search funciona, temos um array de tamanho 8 e queremos encontrar o 0 (pior caso possível). Vai acontecer isso:

[0, 1, 2, 3, 4, 5, 6, 7] // Início (array novinho)
[0, 1, 2, 3] // Primeira iterada
[0, 1] // Segunda iterada
[0] // Final (achamos nosso número)

Claro que na vida real não vamos trabalhar apenas na base 2, mas isso foi apenas para dar aquela clareada na mente e entender o porquê O(log n) é tão bom, outras bases vão deixar a conta bem mais difícil, mas a ideia segue a mesma. Paz.