Big O sem mistério: meu primeiro contato com performance no C#

Se tem uma coisa que todo desenvolvedor já ouviu é: “primeiro faz funcionar, depois otimiza”. E é verdade, não adianta escrever o código mais performático do mundo se ele não resolve o problema.

Mas chega um momento da jornada em que apenas “funcionar” não é suficiente. Foi aí que eu esbarrei na famosa Big O Notation. No começo, parecia um bicho de sete cabeças, cheio de letras e gráficos que não faziam muito sentido. Mas quando comecei a aplicar no meu código, percebi que não era só teoria de faculdade: fazia diferença de verdade no dia a dia.

---

O que é Big O (de forma simples)

A Big O Notation é uma forma de descrever a eficiência de um algoritmo em relação ao crescimento da entrada de dados.

O nome vem de “Order of”, ou seja, a “ordem de crescimento” do algoritmo. O O() que aparece na notação é uma forma matemática de dizer:

“À medida que o número de entradas cresce, o tempo ou espaço necessário pelo algoritmo cresce nessa ordem aqui.”

Então, quando dizemos que um algoritmo é O(n), estamos dizendo que o tempo de execução cresce de forma proporcional ao número de elementos de entrada (n). Já O(1) significa que o tempo não muda, independentemente do tamanho da entrada.

👉 Ou seja, o símbolo O é como um rótulo para indicar qual é a taxa de crescimento do custo do algoritmo.

Não estamos preocupados com o tempo exato em segundos, mas sim com o comportamento quando a quantidade de dados cresce.

---

Principais tipos de Big O com exemplos em C

• O(1) — Constante

Explicação: O tempo não depende do tamanho da entrada.

Prós: É o melhor tipo de complexidade, extremamente rápido e escalável.
Contras: Nem sempre é possível; depende do problema.

Exemplo: Acessar um elemento de um array por índice: arr[5].
Exemplo em C#:

int x = numbers[5];

• O(n) — Linear

Explicação: Cresce proporcionalmente ao número de itens.

Prós: Geralmente aceitável para inputs grandes.
Contras: Pode ser lento se a entrada for gigante.

Exemplo: Percorrer todos os elementos de uma lista:
Exemplo em C#:

foreach (var n in numbers) { 
    Console.WriteLine(n); 
}

• O(n²) — Quadrática

Explicação: Cresce rapidamente por loops aninhados.

Prós: Fácil de implementar, mas geralmente só serve para entradas pequenas.
Contras: Pior tipo de complexidade aqui; não escalável para entradas grandes.

Exemplo: Duplo loop aninhado:
Exemplo em C#:

foreach (var a in numbers) { 
    foreach (var b in numbers) { 
        if(a != b){ /* ... */ }
    }
}

• O(log n) — Logarítmica

Explicação: Cresce devagar, mesmo com entradas grandes.

Prós: Muito eficiente; cresce devagar, mesmo com grandes entradas.
Contras: Normalmente exige que os dados estejam estruturados de forma especial (como árvore ou array ordenado).

Exemplo: Busca binária em um array ordenado.

Exemplo em C#:

int BinarySearch(List<int> list, int target) { 
    int left = 0, right = list.Count - 1; 
    while(left <= right){ 
        int mid = (left + right) / 2; 
        if(list[mid] == target) return mid; 
        if(list[mid] < target) left = mid + 1; 
        else right = mid - 1; 
    } 
    return -1; 
}

• O(n log n) — Linearítmica

Explicação: Mais eficiente que O(n²), usada em ordenação.

Prós: Aceitável para a maioria dos inputs; boa para tarefas como ordenação.
Contras: Mais lento que linear ou logarítmico, mas ainda escalável.

Exemplo: Algoritmos de ordenação eficientes, como MergeSort ou QuickSort (médio caso).
Exemplo em C#:

var sorted = numbers.OrderBy(x => x).ToList();

Gráficos gerados pelo ChatGPT para ajudar a visualizar cada caso.

---

Por que isso importa?

Na prática, Big O me ajudou a entender que nem todo código escala bem.

Dois algoritmos podem resolver exatamente o mesmo problema, mas um deles continua rápido mesmo com milhões de registros, enquanto o outro fica praticamente inutilizável.

Saber disso me fez começar a olhar para meu código de outra forma.

Não era só: “isso funciona?”, mas também: “isso continua funcionando bem quando os dados crescerem 10x ou 100x?”.