Explorador de complexidade Big-O

O Big-O descreve como o trabalho cresce à medida que o tamanho da entrada aumenta. Um único laço cresce aproximadamente com N, laços aninhados costumam crescer com N², e a recursão ramificada pode crescer exponencialmente. A lição importante é a escala: com N pequeno, muitas abordagens parecem semelhantes, mas com N maior, a classe de crescimento domina o tempo de execução.

A forma mais clara de sentir uma classe de crescimento é dobrar a entrada e observar o que acontece com o trabalho. Em O(log N) ele mal se mexe — a busca binária encontra um elemento entre um milhão em cerca de 20 comparações. Em O(N) o trabalho dobra, e em O(N²) quadruplica. Arraste o N nesta ferramenta e veja as diferenças passarem de invisíveis a esmagadoras.

Uma classe de crescimento menor não garante um programa mais rápido. Os cientistas da computação chamam as exceções de algoritmos galácticos: métodos com melhor notação Big-O cujo fator constante oculto é tão enorme que só superam os métodos simples em entradas maiores do que qualquer coisa no universo físico. Vários algoritmos recordistas de multiplicação de matrizes nunca são usados na prática exatamente por isso — o Big-O descarta silenciosamente as constantes que decidem a velocidade real.