Big 0: Medindo Escalabilidade, Não Apenas Complexidade.

Eu vim aqui te dizer que Big O não é uma forma de medir a complexidade de um algoritmo, mas sim sua escalabilidade. Isso mesmo que você leu: Big O mede o quão escalável é seu algoritmo. Ele mede como o tempo de execução (ou consumo de recursos) cresce em função do tamanho da entrada. Muitas pessoas usam a analogia do garçom para explicar o que é uma API. Vou usar essa mesma analogia para explicar minha afirmação.

Imagine que você é um garçom e está chegando uma data muito importante. O restaurante em que você trabalha está com uma grande fila do lado de fora. Seu gerente, surpreso e feliz, pede para você contar quantas pessoas há lá fora. Você, como um funcionário proativo e pensando nas gorjetas, vai correndo verificar.

Existem N formas de você contar quantas pessoas têm na fila. Você pode contar nos dedos, pode pegar uma folha de papel e fazer risquinhos, pode usar o celular para ir anotando... enfim, N possibilidades.

A forma que você escolhe para contar as pessoas na fila pode ser entendida como seu algoritmo. Basicamente, tudo que você escreve quando está programando é um algoritmo. Agora pense: qual das formas que você escolheu é a mais escalável? Se você escolher contar usando os dedos... ok, você vai conseguir se a fila for pequena. Com 10 pessoas, você irá contar rápido. Mas se chegarem mais pessoas e essas 10 virarem 20, 30, 50 pessoas, você terá problemas e irá demorar muito tempo. Apesar de resolver o problema de contar, a forma que você escolheu — seu algoritmo — não tem escala, e agora você precisa pensar em uma forma mais escalável de resolver isso.

Apesar de explicar Big O a fundo não ser o objetivo desta publicação, há certas coisas que temos que revisar/aprender para entender o parágrafo posterior. Uma delas são algumas notações de Big O. Caso você não saiba, O == Big O ou Ordem de Crescimento.

• O(1) – Tempo constante: Esse aqui é o ideal de um algoritmo
  • O tempo de execução não depende do tamanho da entrada. Um exemplo é o acesso a um elemento de um array.
• O(log n) – Tempo logarítmico:
  • O tempo cresce proporcionalmente ao logaritmo do tamanho da entrada. Exemplo: busca binária.
• O(n) – Tempo linear:
  • O tempo cresce proporcionalmente ao tamanho da entrada. Exemplos: percorrer um array.
• O(n log n) – Tempo linearítmico (ou linear vezes logarítmico):
  • Comum em algoritmos de ordenação eficientes, como o Merge Sort e o Heap Sort.
• O(n²) – Tempo quadrático:
  • O tempo cresce proporcionalmente ao quadrado do tamanho da entrada. Exemplos: algoritmos de ordenação ingênuos, como o Bubble Sort (na sua forma básica).
• O(n³) – Tempo cúbico:
  • O tempo cresce com o cubo do tamanho da entrada. Exemplo: algumas soluções de problemas envolvendo matrizes.
• O(2^n) – Tempo exponencial:
  • O tempo de execução dobra a cada incremento na entrada. Exemplos: algoritmos que resolvem problemas de combinatória de forma "brute force".
• O(n!) – Tempo fatorial:
  • O tempo cresce de forma fatorial em relação ao tamanho da entrada. Exemplo clássico: algoritmo que gera todas as permutações de uma sequência.

Agora vamos ver outro exemplo: o uso do ArrayList em Java. Se seu objetivo é acessar elementos por índice, o ArrayList é uma excelente escolha, pois esse acesso é feito em tempo constante — O(1) pelo fato dessa estrutura de dados ter Index em seus elementos. No entanto, se você precisa inserir ou remover elementos em posições aleatórias da lista, essa estrutura pode não ser a melhor opção. Nessas operações, principalmente quando a inserção ou remoção não acontece no final, é necessário mover os elementos subsequentes para acomodar a mudança, resultando em um custo de tempo O(n). Em uma lista pequena, com 10 itens por exemplo, esse custo é desprezível. Mas imagine o impacto ao lidar com 1 milhão de itens. É aí que o Big O se torna fundamental: ele não mede a performance exata (ou o tempo de execução em uma máquina específica), mas sim a escalabilidade do algoritmo — ou seja, como o tempo de execução aumenta conforme o tamanho da entrada cresce.

Entender essas diferenças é muito importante, tanto para entrevistas de emprego quanto para resolver exercícios do LeetCode. E aqui vai um gancho deixado pelo meu último paragrafo e um pouco off-topic. Invistam tempo estudando estrutura de dados, pode parecer um pouco chato e massante no inicio, pois temos sempre aquela emoção de partir para o framework, mas nunca se esqueça que nenhum edifício fica em pé sem uma boa base. Eu vou escrever o que sei sobre isso por aqui e vou usar Java para os exemplos!

Até aqui eu acredito que cumpri a intenção do meu post. Fique a vontade para corrigir algum equivoco ou adicionar algo nos comentários . Eu sou apenas um graduando de Engenharia de Software Tranquilo que esta em busca da sua primeira oportunidade. Aqui esta meu Linkedln caso queiram se conectar: Marcos Vinicius 🤝🏻