Big O em PHP: Guia Completo sobre Complexidade de Tempo (com Exemplos)

Todo desenvolvedor PHP chega, mais cedo ou mais tarde, a um ponto em que o código funciona, mas deixa de escalar. Uma aplicação que parece extremamente rápida com cem registros pode se tornar dolorosamente lenta com cem mil. É exatamente nesse momento que a notação Big O se torna uma das ferramentas mais valiosas no arsenal de um desenvolvedor.

Big O não serve para medir o tempo de execução em milissegundos. Em vez disso, ela nos ajuda a entender como um algoritmo se comporta à medida que a quantidade de dados aumenta. Com esse conhecimento, conseguimos prever gargalos, comparar diferentes implementações e tomar decisões arquiteturais melhores antes que problemas de desempenho apareçam.

Neste guia, você aprenderá a notação Big O sob uma perspectiva prática voltada para PHP. Vamos explorar as classes de complexidade mais comuns, analisar funções do dia a dia da linguagem, otimizar códigos do mundo real e discutir os tipos de perguntas frequentemente feitas em entrevistas técnicas. Ao final, você será capaz de identificar códigos ineficientes, justificar suas decisões de otimização e escrever soluções que escalam com confiança.

O que é Big O?

Quando desenvolvedores dizem que um algoritmo é rápido ou lento, normalmente não estão falando de quantos milissegundos ele leva para executar em um computador específico, mas sim de quão bem ele escala conforme a quantidade de dados aumenta.

É exatamente isso que a notação Big O mede.

Big O descreve como o tempo de execução ou o consumo de memória de um algoritmo cresce à medida que o tamanho da entrada aumenta. Em vez de se concentrar no tempo exato de execução, ela se concentra na taxa de crescimento do algoritmo, permitindo comparar diferentes abordagens independentemente do hardware, da linguagem de programação ou do ambiente de execução.

Por exemplo, imagine que você precisa encontrar um usuário em uma lista.

Se a lista contém apenas dez usuários, praticamente qualquer abordagem parecerá instantânea. Mas o que acontece quando a aplicação passa a ter um milhão de usuários? De repente, o algoritmo escolhido passa a ser muito mais importante do que o processador que está executando o código.

Suponha que você percorra a lista procurando um usuário por vez:

$users = [...];

foreach ($users as $user) {
    if ($user->id === $targetId) {
        return $user;
    }
}

No pior caso, o PHP precisará inspecionar todos os elementos antes de encontrar o usuário correto — ou concluir que ele não existe. Essa operação possui complexidade de tempo O(n), onde n representa o número de elementos.

Agora compare isso com o uso de um array associativo indexado pelo ID do usuário:

$users = [
    101 => $userA,
    102 => $userB,
    103 => $userC,
];

$user = $users[$targetId] ?? null;

Acessar um elemento pela sua chave é, em média, uma operação de tempo constante: O(1).

À medida que o conjunto de dados cresce, a diferença se torna enorme.

Isso ilustra o principal objetivo da notação Big O: ajudar desenvolvedores a prever como um algoritmo se comportará antes que o desempenho se torne um problema.

Também é importante entender o que Big O não mede.

Big O não informa:

• o tempo exato de execução;
• quantos ciclos de CPU um algoritmo utiliza;
• quão rápido o PHP é em comparação com outra linguagem;
• se uma implementação sempre será mais rápida que outra na prática.

Em vez disso, ela responde a uma pergunta muito mais valiosa:

Como este algoritmo escala à medida que o tamanho da entrada aumenta?

É por isso que Big O é um dos conceitos fundamentais da Ciência da Computação e uma habilidade essencial para escrever aplicações escaláveis.

Por que todo desenvolvedor PHP deveria entender Big O?

Muitos desenvolvedores associam Big O apenas a entrevistas de programação ou disciplinas da faculdade, mas seu verdadeiro valor aparece no desenvolvimento de software do dia a dia.

Seja construindo uma aplicação Laravel, um plugin para WordPress, uma API ou um script de linha de comando, toda linha de código que processa coleções de dados possui um custo computacional.

Pequenas ineficiências normalmente passam despercebidas durante o desenvolvimento porque os bancos de dados locais costumam conter poucos registros. No entanto, esses mesmos algoritmos podem se tornar gargalos significativos quando a aplicação entra em produção.

Considere este exemplo:

$selectedIds = [...];

foreach ($users as $user) {
    if (in_array($user->id, $selectedIds)) {
        // Processa o usuário
    }
}

À primeira vista, esse código parece perfeitamente razoável.

O problema é que in_array() realiza uma busca linear sempre que é chamado. Como ele está dentro de outro laço de repetição, a complexidade total passa a ser aproximadamente O(n²).

Uma solução muito mais escalável consiste em transformar o array em uma tabela de consulta (lookup):

$selected = array_flip($selectedIds);

foreach ($users as $user) {
    if (isset($selected[$user->id])) {
        // Processa o usuário
    }
}

Agora a busca é feita em tempo constante, reduzindo a complexidade total para aproximadamente O(n).

A diferença de desempenho se torna enorme à medida que o número de usuários aumenta.

Entender Big O também ajuda você a tomar melhores decisões arquiteturais.

Por exemplo, permite responder perguntas como:

• Devo usar um array associativo indexado ou um array numérico?
• Vale a pena utilizar cache mesmo consumindo mais memória?
• Devo pré-processar os dados antes de iterar sobre eles?
• Um laço aninhado é realmente inevitável?
• Um hash map eliminaria buscas repetidas?

Essas decisões impactam diretamente a escalabilidade da aplicação.

Big O também é extremamente relevante durante revisões de código. Desenvolvedores experientes costumam reconhecer padrões ineficientes imediatamente, porque analisam intuitivamente a complexidade de cada operação em vez de apenas verificar se o código funciona.

Por fim, Big O desempenha um papel importante em entrevistas técnicas.

Muitas empresas pedem aos candidatos que:

• analisem a complexidade de um trecho de código;
• identifiquem gargalos;
• otimizem um algoritmo;
• comparem duas implementações possíveis;
• expliquem os trade-offs entre tempo de execução e consumo de memória.

Ser capaz de discutir esses assuntos com segurança demonstra um entendimento muito mais profundo de engenharia de software do que simplesmente conhecer a sintaxe do PHP.

Em resumo, Big O não trata de escrever algoritmos "inteligentes". Trata-se de escrever software que continua apresentando bom desempenho à medida que sua aplicação cresce.

Complexidade de Tempo vs Complexidade de Espaço

Quando falamos em Big O, a maioria dos desenvolvedores pensa imediatamente em velocidade de execução. No entanto, Big O pode descrever muito mais do que apenas quanto tempo um algoritmo leva para terminar.

Existem duas formas principais de analisar um algoritmo:

• Complexidade de Tempo (Time Complexity) mede como o tempo de execução cresce conforme o tamanho da entrada aumenta.
• Complexidade de Espaço (Space Complexity) mede quanta memória adicional o algoritmo necessita.

Essas duas métricas frequentemente competem entre si.

Em alguns casos, é possível tornar um algoritmo significativamente mais rápido consumindo mais memória. Em outros, é possível economizar memória à custa de uma execução mais lenta.

Complexidade de Tempo

A complexidade de tempo estima como o número de operações cresce à medida que a entrada aumenta.

Por exemplo:

$total = 0;

foreach ($numbers as $number) {
    $total += $number;
}

O laço percorre cada elemento exatamente uma vez.

Se houver:

• 100 números;
• 1.000 números;
• 1.000.000 de números;

o trabalho cresce proporcionalmente.

Isso é O(n).

Agora considere laços aninhados:

foreach ($users as $user) {
    foreach ($orders as $order) {
        // Compara usuário e pedido
    }
}

Se ambas as coleções possuem n elementos, o número de comparações será aproximadamente n × n, resultando em O(n²).

Complexidade de Espaço

A complexidade de espaço mede quanta memória adicional um algoritmo aloca durante sua execução.

Considere este exemplo:

$lookup = [];

foreach ($users as $user) {
    $lookup[$user->id] = $user;
}

O algoritmo cria uma segunda estrutura de dados contendo todos os usuários.

Se houver um milhão de usuários, a tabela de consulta também armazenará um milhão de entradas.

Seu consumo adicional de memória cresce linearmente:

Complexidade de espaço O(n).

Em contraste, este algoritmo utiliza apenas algumas variáveis, independentemente do tamanho da entrada:

$sum = 0;

foreach ($numbers as $number) {
    $sum += $number;
}

Nenhuma coleção adicional é criada.

O consumo de memória permanece praticamente constante:

Complexidade de espaço O(1).

O Trade-off entre Tempo e Memória

Uma das técnicas de otimização mais comuns em engenharia de software consiste em consumir mais memória para reduzir o tempo de execução.

Por exemplo:

Nenhuma das soluções é universalmente melhor.

Se o conjunto de dados possui apenas algumas dezenas de elementos, a implementação mais simples pode ser perfeitamente adequada.

Por outro lado, se a aplicação processa milhões de registros e essa operação é executada milhares de vezes por segundo, investir memória adicional para reduzir a complexidade de tempo quase sempre valerá a pena.

Uma boa engenharia de software consiste em equilibrar esses trade-offs, e não em otimizar cegamente apenas uma das métricas.

Entendendo a Taxa de Crescimento

Um dos maiores equívocos sobre Big O é acreditar que ela mede o tempo de execução de um algoritmo.

Ela não mede.

A notação Big O mede o quão rapidamente o custo de um algoritmo aumenta à medida que a entrada cresce.

Imagine dois algoritmos.

O algoritmo A processa 1.000 elementos em 2 milissegundos.

O algoritmo B processa a mesma quantidade de dados em 10 milissegundos.

À primeira vista, o algoritmo A parece ser mais rápido.

Agora imagine processar um bilhão de elementos.

Se o algoritmo A possui complexidade O(n²) e o algoritmo B possui complexidade O(n log n), o segundo eventualmente se tornará muito mais rápido, mesmo tendo sido mais lento para conjuntos de dados pequenos.

É por isso que engenheiros de software se preocupam muito mais com a taxa de crescimento do que com resultados de benchmark.

A tabela abaixo ilustra como as classes de complexidade mais comuns escalam:

Observe como alguns algoritmos crescem muito lentamente, enquanto outros se tornam inviáveis surpreendentemente rápido.

Outro conceito importante é que Big O ignora constantes.

Os dois algoritmos abaixo possuem a mesma complexidade:

foreach ($items as $item) {
    // ...
}

foreach ($items as $item) {
    // Operação 1
    // Operação 2
    // Operação 3
    // Operação 4
    // Operação 5
}

O segundo laço executa aproximadamente cinco vezes mais trabalho, mas ambos continuam percorrendo cada elemento apenas uma vez.

Sua complexidade continua sendo:

O(n)

Da mesma forma, Big O ignora termos de menor ordem.

Considere este exemplo:

foreach ($users as $user) {
    // O(n)
}

foreach ($orders as $order) {
    // O(n)
}

A complexidade total é:

O(n + n)

Que pode ser simplificada para:

O(2n)

E, finalmente:

O(n)

Da mesma forma:

O(n² + n)

é simplificado para:

O(n²)

porque, à medida que n cresce, o termo quadrático domina completamente o termo linear.

Entender a taxa de crescimento permite analisar a escalabilidade de um algoritmo sem depender de benchmarks ou do hardware utilizado. Em vez de perguntar "Quão rápido esse código roda no meu computador?", você passa a fazer uma pergunta muito mais importante:

"Como esse algoritmo se comportará quando minha aplicação processar dez, mil ou dez milhões de vezes mais dados?"

Essa mudança de perspectiva é justamente o que torna a notação Big O uma ferramenta tão poderosa para projetar software escalável.

As Complexidades Big O Mais Comuns

Nem todos os algoritmos escalam da mesma forma. Alguns permanecem rápidos mesmo processando milhões de registros, enquanto outros se tornam inviáveis com apenas alguns milhares.

Conhecer as principais complexidades Big O permite avaliar rapidamente se uma implementação tende ou não a escalar bem.

A seguir, veremos as classes de complexidade que todo desenvolvedor PHP deveria conhecer.

O(1) — Tempo Constante

Um algoritmo O(1) realiza praticamente a mesma quantidade de trabalho independentemente do tamanho da entrada.

Não importa se o array possui dez elementos ou dez milhões: o número de operações permanece praticamente o mesmo.

Um exemplo clássico é acessar um elemento pelo índice:

$numbers = [10, 20, 30, 40];

$value = $numbers[2];

Ou acessar um array associativo pela chave:

$users = [
    101 => 'Alice',
    102 => 'Bob',
];

$name = $users[101];

Essas operações são consideradas de tempo constante, pois o PHP consegue localizar diretamente a posição onde o valor está armazenado.

Exemplos comuns incluem:

• acessar um índice de um array;
• acessar uma chave de um array associativo;
• isset($array[$key]);
• count() (para arrays);
• strlen() (para strings).

Algoritmos de tempo constante são, em geral, os mais escaláveis.

O(log n) — Tempo Logarítmico

Algoritmos logarítmicos crescem muito lentamente à medida que a entrada aumenta.

Em vez de verificar cada elemento individualmente, eles eliminam metade das possibilidades a cada etapa.

O exemplo clássico é a Busca Binária (Binary Search).

Imagine procurar uma palavra em um dicionário.

Você não começa pela primeira página. Em vez disso, abre aproximadamente no meio, verifica se a palavra procurada vem antes ou depois daquela página, descarta metade do livro e repete o processo.

A cada passo, metade das possibilidades é eliminada.

Mesmo para um milhão de elementos, uma busca binária precisa de apenas cerca de 20 comparações.

Embora o PHP não possua uma função nativa para busca binária, implementá-la sobre um array ordenado é bastante simples.

Entretanto, a busca binária só funciona em dados previamente ordenados.

Imagine que você esteja procurando o número 42 em um array ordenado contendo um milhão de inteiros. Em vez de verificar cada elemento individualmente, a busca binária começa analisando o elemento central:

• Se o valor central for menor que 42, toda a metade inferior é descartada.
• Se for maior, toda a metade superior é descartada.
• O processo continua até encontrar o valor ou concluir que ele não existe.

Como o espaço de busca é reduzido pela metade a cada iteração, a complexidade é logarítmica.

function binarySearch(array $numbers, int $target): ?int
{
    $left = 0;
    $right = count($numbers) - 1;

    while ($left <= $right) {
        $middle = intdiv($left + $right, 2);

        if ($numbers[$middle] === $target) {
            return $middle;
        }

        if ($numbers[$middle] < $target) {
            $left = $middle + 1;
        } else {
            $right = $middle - 1;
        }
    }

    return null;
}

$numbers = [3, 7, 12, 18, 24, 31, 42, 56, 67, 81];

$index = binarySearch($numbers, 42);

echo $index; // 6

O(n) — Tempo Linear

Um algoritmo O(n) percorre cada elemento exatamente uma vez.

Se o tamanho da entrada dobrar, o trabalho realizado também dobrará aproximadamente.

Por exemplo:

$total = 0;

foreach ($numbers as $number) {
    $total += $number;
}

Ou realizando uma busca:

foreach ($users as $user) {
    if ($user->id === $id) {
        return $user;
    }
}

Diversas funções nativas do PHP possuem complexidade linear, como:

• in_array();
• array_search();
• array_filter();
• array_map();
• array_reduce().

Algoritmos lineares são perfeitamente aceitáveis na maioria das aplicações e, muitas vezes, inevitáveis.

O(n log n) — Tempo Linearítmico

Essa complexidade aparece em diversos algoritmos eficientes de ordenação.

O algoritmo continua processando todos os elementos, mas também realiza um trabalho logarítmico adicional.

A maioria dos algoritmos de ordenação baseados em comparação pertence a essa categoria, incluindo:

• Merge Sort;
• Heap Sort;
• Quick Sort (caso médio).

As funções nativas de ordenação do PHP, como:

sort($numbers);

e

usort($users, $comparator);

normalmente executam em O(n log n).

Embora sejam mais lentas do que algoritmos lineares, continuam escalando muito bem e representam o melhor desempenho possível para ordenações baseadas em comparação.

O(n²) — Tempo Quadrático

Algoritmos quadráticos executam uma quantidade de trabalho proporcional ao quadrado do tamanho da entrada.

Eles normalmente surgem quando um laço está aninhado dentro de outro.

Exemplo:

foreach ($users as $user) {
    foreach ($orders as $order) {
        // Compara usuário e pedido
    }
}

Se cada array possuir 10.000 elementos, o número de comparações poderá chegar a 100 milhões.

Outro exemplo bastante comum é utilizar in_array() dentro de um laço:

foreach ($users as $user) {
    if (in_array($user->id, $selectedIds)) {
        // ...
    }
}

Esse padrão aparece com frequência em aplicações reais e costuma se tornar um gargalo de desempenho.

Sempre que possível, substituir buscas lineares repetidas por consultas em um hash map pode reduzir a complexidade para O(n).

O(2ⁿ) — Tempo Exponencial

Algoritmos exponenciais dobram a quantidade de trabalho sempre que a entrada aumenta em apenas uma unidade.

Esse crescimento rapidamente se torna inviável.

Por exemplo:

Soluções recursivas de força bruta frequentemente possuem complexidade exponencial.

Exemplo:

function fibonacci(int $n): int
{
    if ($n <= 1) {
        return $n;
    }

    return fibonacci($n - 1) + fibonacci($n - 2);
}

Essa implementação recalcula repetidamente os mesmos valores, provocando crescimento exponencial.

Utilizando memoização ou programação dinâmica, essa complexidade pode ser reduzida drasticamente.

O(n!) — Tempo Fatorial

A complexidade fatorial é ainda pior do que a exponencial.

Algoritmos desse tipo geram todas as possíveis combinações ou permutações de um conjunto de dados.

Por exemplo, encontrar todas as possíveis ordenações de dez objetos exige:

10! = 3.628.800

Já para quinze objetos:

15! ≈ 1,3 trilhão

Problemas envolvendo permutações, busca exaustiva ou o Problema do Caixeiro Viajante costumam apresentar complexidade fatorial.

Felizmente, a maioria das aplicações web nunca precisará executar algoritmos tão caros.

Comparação das Complexidades

Como regra geral:

• O(1) e O(log n) são as complexidades ideais.
• O(n) costuma ser perfeitamente aceitável.
• O(n log n) é o esperado para algoritmos de ordenação.
• O(n²) merece atenção e deve ser analisado cuidadosamente.
• O(2ⁿ) e O(n!) normalmente devem ser evitados, a menos que o próprio problema exija esse tipo de solução.

Comparação Visual das Complexidades Big O

Uma das maneiras mais fáceis de entender Big O é visualizar como diferentes algoritmos crescem à medida que o tamanho da entrada aumenta.

A tabela abaixo mostra o número aproximado de operações necessárias para as classes de complexidade mais comuns.

Observe como algoritmos logarítmicos crescem muito mais lentamente do que algoritmos quadráticos ou exponenciais.

Outra forma útil de enxergar a complexidade é imaginar o que acontece quando o tamanho da entrada dobra.

É por isso que desenvolvedores experientes dão muito mais importância à complexidade algorítmica do que a resultados de benchmark. Uma implementação que parece um pouco mais lenta hoje pode superar outra por várias ordens de grandeza conforme a aplicação cresce.

Big O em Arrays do PHP

Os arrays são uma das funcionalidades mais poderosas do PHP. No entanto, muitos desenvolvedores assumem que todas as operações sobre arrays possuem o mesmo custo — o que está longe de ser verdade.

Conhecer a complexidade das operações mais comuns ajuda você a escrever código mais eficiente e evitar gargalos de desempenho sem perceber.

Observação: os arrays do PHP são implementados internamente como tabelas hash ordenadas (Ordered Hash Tables). Isso significa que eles combinam características de arrays tradicionais e de hash maps, fazendo com que algumas operações sejam executadas em tempo constante, enquanto outras exigem percorrer ou copiar o array.

Acesso

Acessar um elemento pelo índice ou pela chave normalmente é uma operação de tempo constante.

$numbers = [10, 20, 30];

echo $numbers[1];

Complexidade:

O(1)

O mesmo vale para arrays associativos.

Busca

Buscar um valor exige percorrer o array até que o elemento seja encontrado.

if (in_array(30, $numbers)) {
    // ...
}

Ou:

$key = array_search(30, $numbers);

Complexidade:

O(n)

No pior caso, o PHP precisará verificar todos os elementos.

Inserção

Adicionar um elemento ao final do array normalmente é uma operação de tempo constante.

$numbers[] = 50;

Complexidade média:

O(1)

Entretanto, inserir um elemento no início exige deslocar todos os demais elementos.

array_unshift($numbers, 5);

Complexidade:

O(n)

Da mesma forma, inserir elementos no meio do array normalmente exige mover todos os elementos subsequentes.

Remoção

Remover o último elemento é uma operação barata.

array_pop($numbers);

Complexidade:

O(1)

Já remover o primeiro elemento é significativamente mais caro, pois todos os demais precisam ser reindexados.

array_shift($numbers);

Complexidade:

O(n)

Remover um elemento em uma posição intermediária também costuma exigir o deslocamento dos elementos restantes.

Resumo

Entender esses custos ajuda a explicar por que operações próximas ao início de arrays grandes costumam ser muito mais lentas do que operações realizadas no final.

Big O em Arrays Associativos (Hash Maps)

Um dos maiores pontos fortes do PHP é sua implementação de arrays associativos.

Internamente, o PHP utiliza uma tabela hash (Hash Table), permitindo que uma chave seja mapeada diretamente para seu respectivo valor.

Em vez de percorrer o array sequencialmente, o PHP calcula o hash da chave e acessa diretamente a posição correspondente.

Isso torna arrays associativos extremamente eficientes para consultas.

$users = [
    101 => 'Alice',
    102 => 'Bob',
    103 => 'Charlie',
];

echo $users[102];

Complexidade média:

O(1)

Verificar se uma chave existe também é uma operação de tempo constante.

if (isset($users[$id])) {
    // ...
}

Complexidade:

O(1)

Esse é um dos principais motivos pelos quais isset() costuma ser muito mais rápido do que in_array().

Considere o seguinte código:

foreach ($users as $user) {
    if (in_array($user->id, $selectedIds)) {
        // ...
    }
}

Cada iteração executa uma busca linear, resultando em aproximadamente:

O(n²)

Uma abordagem muito melhor consiste em criar uma tabela de consulta antes.

$selected = array_flip($selectedIds);

foreach ($users as $user) {
    if (isset($selected[$user->id])) {
        // ...
    }
}

Agora cada consulta passa a ser executada em tempo constante, reduzindo a complexidade total para aproximadamente:

O(n)

Esse tipo de otimização é amplamente utilizado em sistemas de produção que processam grandes volumes de IDs, permissões, produtos, usuários ou registros de banco de dados.

Operações Comuns em Hash Maps

Embora colisões de hash possam, teoricamente, degradar o desempenho para O(n), a implementação do PHP foi projetada para manter consultas muito próximas de tempo constante em aplicações reais.

Por isso, sempre que você perceber que está realizando buscas repetidas dentro de arrays grandes, vale a pena fazer uma pergunta simples:

Esta coleção pode ser transformada em um hash map?

Na maioria das vezes, a resposta para essa pergunta leva a uma das maiores otimizações de desempenho que você pode fazer com apenas algumas linhas de código.

Laços de Repetição e Laços Aninhados

Os laços de repetição são uma das formas mais simples de estimar a complexidade de um algoritmo.

Como regra geral:

• Um único laço normalmente possui complexidade O(n).
• Dois laços consecutivos continuam sendo O(n).
• Laços aninhados frequentemente resultam em O(n²).
• A complexidade depende de quantas vezes cada laço é executado.

Vamos analisar os cenários mais comuns.

Um Único Laço — O(n)

Um laço que percorre cada elemento exatamente uma vez possui complexidade linear.

$total = 0;

foreach ($numbers as $number) {
    $total += $number;
}

Complexidade:

O(n)

O número de operações cresce proporcionalmente ao número de elementos.

Laços Consecutivos — Ainda O(n)

Alguns desenvolvedores acreditam que dois laços automaticamente significam O(n²).

Isso não é verdade.

foreach ($users as $user) {
    // Processa usuários
}

foreach ($orders as $order) {
    // Processa pedidos
}

A complexidade é:

O(n + n)

Que pode ser simplificada para:

O(n)

Isso acontece porque Big O ignora fatores constantes.

Laços Aninhados — O(n²)

Quando um laço interno é executado completamente para cada iteração do laço externo, a complexidade se torna quadrática.

foreach ($users as $user) {
    foreach ($orders as $order) {
        if ($user->id === $order->userId) {
            // ...
        }
    }
}

Complexidade:

O(n²)

Com 100 usuários e 100 pedidos, podem ocorrer até 10.000 comparações.

Com 10.000 usuários e 10.000 pedidos, esse número sobe para 100 milhões de comparações.

Laços Aninhados Nem Sempre São O(n²)

A complexidade depende de quantas vezes o laço interno é executado.

Considere este exemplo:

for ($i = 0; $i < $n; $i++) {
    for ($j = $i; $j < $n; $j++) {
        // ...
    }
}

Embora o segundo laço execute menos iterações a cada passagem do primeiro, a complexidade total continua sendo quadrática.

Agora observe este outro exemplo:

$i = 1;

while ($i < $n) {
    $i *= 2;
}

A cada iteração, o valor de $i é dobrado.

Complexidade:

O(log n)

A principal lição é que apenas olhar para a quantidade de laços não é suficiente para determinar a complexidade. O que realmente importa é quantas vezes eles são executados.

Interrompendo o Laço Antecipadamente

Em alguns casos, um laço pode terminar antes de percorrer todos os elementos.

foreach ($users as $user) {
    if ($user->id === $targetId) {
        break;
    }
}

Melhor caso:

O(1)

Pior caso:

O(n)

Por padrão, Big O normalmente descreve o pior caso, a menos que seja informado explicitamente o contrário.

Resumo

Sempre que encontrar laços aninhados, vale a pena fazer uma pergunta simples:

É possível substituir um desses laços por uma consulta em um hash map?

Em muitos casos, a resposta reduz a complexidade de O(n²) para O(n).

Funções Comuns do PHP e Suas Complexidades

Conhecer a complexidade das funções nativas do PHP ajuda a identificar gargalos de desempenho antes que eles se tornem um problema.

A tabela abaixo resume a complexidade média de algumas das funções mais utilizadas.

Vamos analisar as mais importantes.

in_array()

if (in_array($id, $ids)) {
    // ...
}

Complexidade:

O(n)

O PHP percorre os elementos um a um até encontrar uma correspondência.

array_search()

$key = array_search($id, $ids);

Complexidade:

O(n)

No pior caso, todo o array precisará ser percorrido.

isset()

isset($users[$id]);

Complexidade:

O(1)

É uma das operações de consulta mais rápidas disponíveis no PHP.

array_key_exists()

array_key_exists($id, $users);

Complexidade:

O(1)

Diferentemente de isset(), essa função também retorna true quando a chave existe, mas seu valor é null.

$users = [
    1 => null,
];

isset($users[1]);             // false
array_key_exists(1, $users);  // true

sort() e usort()

Os algoritmos de ordenação normalmente executam em:

O(n log n)

Independentemente da função de comparação utilizada.

array_merge()

$result = array_merge($a, $b);

Complexidade:

O(n)

O array resultante precisa ser reconstruído, exigindo a cópia de todos os elementos.

array_unique()

$result = array_unique($values);

Complexidade média:

O(n)

O PHP utiliza hashing internamente para detectar valores duplicados de forma eficiente.

array_flip()

$lookup = array_flip($ids);

Complexidade:

O(n)

Embora a criação da tabela de consulta exija uma passagem completa pelo array, todas as consultas realizadas posteriormente passam a ser executadas em tempo constante.

array_map() e array_filter()

$result = array_map(
    fn ($user) => $user->name,
    $users
);

$active = array_filter(
    $users,
    fn ($user) => $user->active
);

Ambas percorrem todos os elementos exatamente uma vez.

Complexidade:

O(n)

Exemplos Práticos

A teoria é importante, mas Big O fica muito mais fácil de entender quando aplicada a situações reais do dia a dia.

Os exemplos a seguir demonstram alguns gargalos de desempenho comuns e como podemos resolvê-los.

Encontrando Valores Duplicados

Uma abordagem bastante comum entre iniciantes consiste em comparar cada elemento com todos os demais.

$duplicates = [];

foreach ($numbers as $i => $a) {
    foreach ($numbers as $j => $b) {
        if ($i !== $j && $a === $b) {
            $duplicates[] = $a;
        }
    }
}

Complexidade:

O(n²)

Uma solução muito mais eficiente utiliza um hash map.

$seen = [];
$duplicates = [];

foreach ($numbers as $number) {
    if (isset($seen[$number])) {
        $duplicates[] = $number;
    } else {
        $seen[$number] = true;
    }
}

Complexidade:

O(n)

Removendo Valores Duplicados

O próprio PHP já oferece uma solução otimizada para esse problema.

$result = array_unique($numbers);

Complexidade média:

O(n)

Tentar remover duplicatas manualmente utilizando laços aninhados normalmente resultaria em uma complexidade O(n²).

Contando Frequências

Suponha que você precise contar quantas vezes cada palavra aparece em um texto.

$counts = [];

foreach ($words as $word) {
    $counts[$word] = ($counts[$word] ?? 0) + 1;
}

Complexidade:

O(n)

Esse padrão aparece com frequência na geração de relatórios, análises estatísticas, dashboards e sistemas de métricas.

Buscando Usuários

Abordagem ineficiente:

foreach ($users as $user) {
    if ($user->id === $targetId) {
        return $user;
    }
}

Complexidade:

O(n)

Abordagem otimizada:

$userMap = [];

foreach ($users as $user) {
    $userMap[$user->id] = $user;
}

return $userMap[$targetId] ?? null;

Criar o mapa de consulta possui complexidade:

O(n)

Cada consulta realizada posteriormente possui complexidade:

O(1)

Essa otimização se torna extremamente vantajosa quando diversos usuários precisam ser consultados ao longo da execução da aplicação.

Paginação

Muitos desenvolvedores carregam todo o conjunto de dados em memória antes de paginá-lo.

$page = array_slice($users, $offset, $limit);

Embora array_slice() seja relativamente eficiente, o verdadeiro problema normalmente acontece antes:

$users = $repository->findAll();

Carregar um milhão de registros apenas para exibir vinte é muito mais custoso do que deixar o banco de dados realizar a paginação.

Uma abordagem melhor é:

SELECT *
FROM users
LIMIT 20 OFFSET 100;

Sempre que possível, filtre, ordene e pagine os dados o mais próximo possível da fonte dos dados, em vez de processar registros desnecessários em PHP.

Como Otimizar Código PHP Utilizando Big O

Big O é muito mais do que um conceito teórico: ela fornece diretrizes práticas para escrever aplicações PHP mais rápidas e escaláveis.

O objetivo não é otimizar cada linha de código prematuramente, mas reconhecer padrões que se tornam caros conforme o volume de dados cresce.

Veja algumas das estratégias mais eficazes.

Prefira Consultas em Hash Maps em vez de Buscas Lineares

Em vez de percorrer repetidamente um array:

in_array($id, $ids);

Crie uma tabela de consulta apenas uma vez.

$lookup = array_flip($ids);

isset($lookup[$id]);

Essa é uma das otimizações mais impactantes que podem ser feitas em PHP.

Evite Laços Aninhados Sempre que Possível

Laços aninhados costumam indicar que um hash map ou uma etapa de pré-processamento pode reduzir significativamente a complexidade.

Em vez de:

foreach ($users as $user) {
    foreach ($permissions as $permission) {
        // ...
    }
}

Considere criar primeiro uma estrutura indexada para consultas rápidas.

Escolha a Estrutura de Dados Adequada

Nem toda coleção deve ser representada por um array numérico.

Sempre que fizer sentido, utilize:

• arrays associativos para consultas rápidas;
• listas para dados sequenciais;
• estruturas especializadas da SPL (SplQueue, SplStack, SplPriorityQueue, etc.) quando apropriado.

A escolha da estrutura de dados costuma ter muito mais impacto no desempenho do que pequenas micro-otimizações.

Ordene Apenas Quando Necessário

Ordenar dados é uma operação relativamente cara.

Evite código como:

sort($items);

dentro de laços ou em operações repetidas, a menos que a ordenação seja realmente necessária.

Sempre que possível, deixe que o banco de dados entregue os registros já ordenados.

Evite Recalcular o Mesmo Resultado

Se um cálculo caro é executado repetidamente, tente realizá-lo apenas uma vez.

Em vez de:

foreach ($users as $user) {
    $permissions = getPermissions($user);
}

Considere utilizar cache, pré-processamento ou carregamento antecipado (preloading), quando fizer sentido.

Repetir o mesmo trabalho diversas vezes é uma das causas mais comuns de ineficiência escondida.

Deixe o Banco de Dados Fazer o Trabalho Pesado

Bancos de dados são altamente otimizados para realizar buscas, ordenações, filtros, agrupamentos e agregações sobre grandes volumes de dados.

Em vez de carregar todos os registros para filtrá-los em PHP:

$users = $repository->findAll();

$active = array_filter(
    $users,
    fn ($user) => $user->active
);

Utilize SQL:

SELECT *
FROM users
WHERE active = 1;

Mover esse processamento para o banco de dados normalmente reduz tanto o tempo de execução quanto o consumo de memória.

Meça Antes de Otimizar

Big O prevê a escalabilidade de um algoritmo, mas apenas ferramentas de profiling mostram onde estão os gargalos reais.

Antes de reescrever um trecho de código, faça algumas perguntas:

• Este código realmente está lento?
• O conjunto de dados é grande o suficiente para justificar uma otimização?
• Essa função é executada com frequência?
• Uma solução mais simples seria mais fácil de manter?

Otimização prematura pode tornar o código mais complexo sem trazer benefícios significativos.

Pense em Escalabilidade

Talvez o hábito mais valioso seja fazer uma pergunta simples sempre que escrever um algoritmo:

O que acontecerá se esta coleção crescer de cem elementos para um milhão?

Essa forma de pensar naturalmente leva a melhores decisões arquiteturais, código mais eficiente e aplicações capazes de continuar performando bem à medida que crescem.

É justamente essa capacidade de raciocinar sobre escalabilidade — e não apenas de escrever código funcional — que diferencia engenheiros de software experientes de desenvolvedores focados apenas na implementação.

Erros Comuns

Entender Big O é uma coisa; aplicá-la corretamente é outra completamente diferente. Muitos problemas de desempenho em aplicações reais surgem devido a alguns equívocos recorrentes, e não por causa de algoritmos particularmente complexos.

Veja alguns dos erros mais comuns.

Erro #1: Otimizar Prematuramente

Um dos princípios mais conhecidos da engenharia de software diz:

"Premature optimization is the root of all evil."

— Donald Knuth

("A otimização prematura é a raiz de todo mal.")

Muitos desenvolvedores passam horas substituindo um código simples e legível por implementações muito mais complexas apenas para economizar alguns milissegundos em operações executadas poucas vezes.

Por exemplo:

foreach ($users as $user) {
    // ...
}

Não existe absolutamente nada de errado com um algoritmo O(n).

Se a coleção possui apenas algumas centenas de elementos e o código é executado uma única vez por requisição, a solução mais simples provavelmente continuará sendo a melhor.

Otimize apenas onde o desempenho realmente importa.

Erro #2: Ignorar a Complexidade Algorítmica

O erro oposto é acreditar que hardware moderno resolve qualquer problema de desempenho.

Código como este normalmente funciona perfeitamente durante o desenvolvimento:

foreach ($users as $user) {
    if (in_array($user->id, $selectedIds)) {
        // ...
    }
}

Até que um dia:

• $users passa a conter 500.000 registros;
• $selectedIds contém 100.000 IDs;
• a requisição passa a levar vários segundos para ser concluída.

Entender Big O ajuda a identificar esses gargalos antes que eles cheguem à produção.

Erro #3: Achar que Todo Laço Aninhado é Ruim

Laços aninhados costumam ser associados à complexidade O(n²), mas nem sempre isso é verdade.

Por exemplo:

foreach ($users as $user) {
    foreach ($user->roles as $role) {
        // ...
    }
}

Se cada usuário possui apenas duas ou três permissões, o laço interno executa praticamente um número constante de vezes.

Nesse caso, a complexidade fica muito mais próxima de:

O(n)

O importante não é a quantidade de laços, mas sim o número total de iterações realizadas.

Erro #4: Ignorar a Complexidade de Espaço

Muitos desenvolvedores se preocupam apenas com tempo de execução.

Entretanto, reduzir um algoritmo de O(n²) para O(n) frequentemente exige criar uma estrutura auxiliar.

$lookup = array_flip($ids);

Essa solução consome mais memória, mas reduz drasticamente o tempo gasto nas consultas.

Otimização quase sempre envolve um equilíbrio entre tempo de CPU, consumo de memória, legibilidade e facilidade de manutenção.

Erro #5: Escolher a Estrutura de Dados Errada

Muitos desenvolvedores resolvem todos os problemas utilizando arrays numéricos.

Entretanto, quando a operação principal é buscar elementos pelo ID, um array associativo costuma ser uma escolha muito melhor.

Em vez de:

[
    ['id' => 101, 'name' => 'Alice'],
    ['id' => 102, 'name' => 'Bob'],
]

Considere:

[
    101 => $alice,
    102 => $bob,
]

A diferença entre consultas O(n) e O(1) pode ser gigantesca.

Erro #6: Confundir Big O com Tempo de Execução

Big O não responde perguntas como:

• "Esse código executará em 15 milissegundos?"
• "PHP é mais rápido que Go?"
• "Laravel é mais lento que Symfony?"

Ela apenas descreve como um algoritmo escala conforme o tamanho da entrada aumenta.

Um algoritmo teoricamente pior pode ser mais rápido para conjuntos de dados pequenos e tornar-se muito mais lento conforme os dados crescem.

Erro #7: Ignorar as Funções Nativas do PHP

A biblioteca padrão do PHP vem sendo otimizada há décadas.

Mesmo assim, muitos desenvolvedores implementam manualmente algoritmos de ordenação, remoção de duplicatas ou filtragem quando a linguagem já oferece funções altamente otimizadas para essas tarefas.

Antes de reinventar a roda, verifique se o PHP já não possui uma solução pronta, eficiente e amplamente testada.

Big O em Entrevistas Técnicas

Se você já participou de uma entrevista para uma vaga de backend ou engenharia de software, provavelmente já se deparou com perguntas sobre Big O.

Na maioria dos casos, os entrevistadores não estão interessados em saber se você decorou a complexidade de cada algoritmo, mas sim em como você raciocina.

Eles querem avaliar se você consegue:

• identificar algoritmos ineficientes;
• estimar a complexidade de um código;
• explicar os trade-offs envolvidos;
• melhorar uma solução existente.

Veja algumas das perguntas mais comuns.

"Qual é a complexidade deste código?"

Você pode receber algo como:

foreach ($users as $user) {
    foreach ($orders as $order) {
        if ($user->id === $order->userId) {
            // ...
        }
    }
}

Uma boa resposta explicaria que os laços aninhados produzem aproximadamente:

O(n²)

e sugeriria substituir uma das coleções por um hash map para eliminar a busca repetitiva.

"Você consegue otimizar esse código?"

Os entrevistadores frequentemente esperam uma transformação parecida com esta.

Antes:

foreach ($users as $user) {
    if (in_array($user->id, $selectedIds)) {
        // ...
    }
}

Depois:

$selected = array_flip($selectedIds);

foreach ($users as $user) {
    if (isset($selected[$user->id])) {
        // ...
    }
}

Ser capaz de explicar por que a segunda solução escala melhor costuma ser mais importante do que simplesmente escrevê-la.

"Quais são os trade-offs?"

Uma resposta forte reconhece os dois lados da decisão.

Por exemplo:

• consultas muito mais rápidas;
• maior consumo de memória;
• código ligeiramente mais complexo.

Entrevistadores valorizam candidatos que entendem que otimizações quase nunca são gratuitas.

"Você consegue estimar a complexidade sem executar o código?"

Essa é uma habilidade extremamente importante.

Você deve ser capaz de estimar a complexidade apenas lendo a implementação.

Esse tipo de análise fica muito mais simples quando você aprende a reconhecer alguns padrões recorrentes:

• um único laço → O(n);
• busca binária → O(log n);
• ordenação → O(n log n);
• laços aninhados → normalmente O(n²);
• recursão → depende da estrutura da chamada recursiva.

O Que os Entrevistadores Realmente Procuram

Muitos candidatos decoram tabelas de complexidade.

Os melhores candidatos conseguem explicar por que um algoritmo possui determinada complexidade, discutir possíveis otimizações e avaliar se essas otimizações realmente fazem sentido.

Essa capacidade demonstra maturidade em engenharia de software, e não apenas memorização de conceitos.

Perguntas Frequentes

O(n) é sempre ruim?

Não.

A maioria das aplicações reais contém diversos algoritmos O(n).

Na prática, a complexidade linear costuma ser a melhor solução possível quando todos os elementos precisam ser processados.

O(1) é sempre possível?

Não.

Alguns problemas exigem, por natureza, que todos os elementos sejam percorridos.

Por exemplo, calcular a soma de um array não pode ser feito sem visitar cada um de seus valores.

O(log n) é mais rápido que O(n)?

Quase sempre, quando trabalhamos com conjuntos de dados suficientemente grandes.

Para um milhão de elementos:

• O(log n) realiza aproximadamente 20 operações.
• O(n) realiza aproximadamente um milhão de operações.

Essa diferença se torna gigantesca conforme o volume de dados aumenta.

Por que isset() costuma ser muito mais rápido que in_array()?

isset() realiza uma consulta em uma tabela hash utilizando uma chave.

Já in_array() percorre os valores do array sequencialmente até encontrar uma correspondência.

Complexidade média:

Devo sempre otimizar pensando em Big O?

Não.

Legibilidade, facilidade de manutenção e simplicidade também são fatores importantes.

Um algoritmo teoricamente mais eficiente, mas muito difícil de compreender, pode não ser a melhor escolha para um conjunto pequeno de dados.

Big O se aplica apenas a algoritmos?

Não.

Ela pode ser aplicada praticamente a qualquer operação envolvendo dados, incluindo:

• buscas;
• ordenações;
• filtros;
• índices de banco de dados;
• cache;
• operações de rede;
• operações em sistemas de arquivos;
• estruturas de dados.

Big O garante desempenho no mundo real?

Não por si só.

O desempenho real também depende de diversos outros fatores, como:

• hardware;
• hierarquia de memória (cache, RAM etc.);
• otimizações do compilador ou interpretador;
• versão do PHP;
• extensões utilizadas;
• sistema operacional;
• eficiência dos caches.

Big O prevê a escalabilidade de um algoritmo, não o tempo exato de execução.

Conclusão

A notação Big O é muito mais do que um conceito acadêmico ou um assunto reservado para entrevistas técnicas. Ela oferece uma maneira prática de compreender como um software se comporta à medida que a aplicação cresce e passa a processar volumes cada vez maiores de dados.

Ao longo deste guia, vimos como as principais classes de complexidade escalam, por que a taxa de crescimento é mais importante do que o tempo bruto de execução e como o código PHP do dia a dia pode ser otimizado simplesmente escolhendo algoritmos ou estruturas de dados mais adequados.

Talvez a principal lição seja que desempenho raramente depende de escrever código "genial". Na maioria das vezes, trata-se de reconhecer padrões ineficientes — como buscas lineares repetidas ou laços aninhados desnecessários — e substituí-los por soluções mais escaláveis, como consultas em hash maps.

Como desenvolvedor PHP, você não precisa decorar todas as fórmulas de complexidade. Em vez disso, desenvolva o hábito de fazer algumas perguntas simples sempre que escrever ou revisar um algoritmo:

• Quantas vezes este laço será executado?
• Estou realizando a mesma busca repetidamente?
• Outra estrutura de dados tornaria esta operação mais eficiente?
• O que acontecerá se este conjunto crescer de algumas centenas para milhões de registros?

Essas perguntas naturalmente levam a melhores decisões arquiteturais, código mais fácil de manter e aplicações que continuam apresentando bom desempenho mesmo sob cargas muito maiores.

No fim das contas, dominar Big O não significa apenas impressionar entrevistadores — embora isso certamente ajude. Significa construir software que escala de forma elegante, resolver problemas com eficiência e se tornar o tipo de engenheiro que entende não apenas como um código funciona, mas principalmente por que uma solução é fundamentalmente melhor do que outra.