A análise de algoritmos estuda como medir, comparar e prever o custo de procedimentos computacionais. Quando resolvemos um problema por software, não basta apenas obter uma resposta correta; também importa saber quanto tempo o algoritmo leva, quanta memória consome, como se comporta em entradas grandes e quais limites teóricos restringem possíveis melhorias. Essa área faz a ponte entre programação prática, modelagem matemática e teoria da computação.

Em ciência da computação, a análise de algoritmos é central porque praticamente todo sistema real precisa lidar com restrições de desempenho. Um compilador precisa processar programas grandes em tempo razoável; um banco de dados precisa responder consultas sob carga; um sistema de busca precisa examinar enormes volumes de informação; um algoritmo de criptografia precisa ser seguro, mas também executável; e um sistema embarcado pode ter limites rígidos de memória e tempo. Em todos esses casos, escolher um algoritmo inadequado pode tornar a solução inviável, mesmo quando o hardware é moderno.

O capítulo começa pelas medidas de complexidade e pela ideia de crescimento assintótico, passa pelas notações formais usadas para expressar limites superiores e inferiores, discute medições empíricas de performance e depois aborda recorrências e análise de algoritmos iterativos e recursivos. O objetivo é formar uma base para responder perguntas como: qual algoritmo cresce mais lentamente? quando duas soluções têm a mesma ordem de grandeza? o que significa dizer que um algoritmo é assintoticamente ótimo? e até onde é possível melhorar um problema?

Quando estudamos um algoritmo, queremos responder a perguntas quantitativas: como o tempo de execução cresce com o tamanho da entrada $n$? quanta memória adicional é necessária? o algoritmo continua viável quando a entrada dobra, triplica ou chega a milhões de elementos? A análise de complexidade procura modelar esse crescimento de forma matemática, permitindo comparar soluções sem depender apenas de testes empíricos.

As duas medidas mais importantes são a complexidade de tempo e a complexidade de espaço. A primeira estima a quantidade de operações executadas; a segunda estima quanta memória extra o algoritmo precisa além da entrada. Em muitos problemas, existe um trade-off entre essas duas dimensões: podemos gastar mais memória para reduzir tempo, ou aceitar mais tempo para poupar espaço.

Antes de falar em formas de crescimento, vale esclarecer a ideia de tarefa algorítmica. Buscar significa procurar um elemento, valor ou registro dentro de uma estrutura de dados. Ordenar significa reorganizar os dados segundo algum critério. Contar, selecionar, particionar e percorrer também são operações muito comuns. Cada uma delas pode ser implementada de várias maneiras, e é justamente essa diferença de estratégia que a análise de algoritmos tenta comparar.

Se um algoritmo percorre um vetor uma única vez, é natural esperar crescimento aproximadamente linear. Dizemos que esse crescimento é linear porque o custo aumenta na mesma proporção que o tamanho da entrada: se dobramos a quantidade de elementos, esperamos aproximadamente o dobro de trabalho; se triplicamos a entrada, esperamos aproximadamente o triplo. Se um algoritmo compara todos os pares de elementos, o custo tende a crescer quadraticamente. Se divide o problema em partes e reduz o tamanho pela metade a cada passo, podem aparecer comportamentos logarítmicos. A ideia central não é contar ciclos exatos do processador, mas entender a tendência dominante de crescimento.

Por exemplo, considere a busca linear em um vetor não ordenado com $n$ elementos. Nesse caso, o algoritmo verifica os itens um a um, em sequência, começando do primeiro e avançando até encontrar o valor procurado ou chegar ao fim da estrutura. Ela é chamada linear exatamente porque, no pior caso, o número de verificações cresce proporcionalmente a $n$. Já em uma busca binária sobre vetor ordenado, a cada comparação descartamos metade do espaço restante, o que leva a um crescimento muito mais lento:

$$ n,\ \frac{n}{2},\ \frac{n}{4},\ \frac{n}{8},\ \ldots $$

Busca binária exige uma estrutura ordenada porque sua lógica depende de comparar o elemento central com o alvo e decidir se a resposta só pode estar à esquerda ou à direita. Esse contraste mostra por que a análise assintótica é tão importante: duas soluções corretas podem ter custos drasticamente diferentes quando a entrada cresce.

Na prática, o tempo medido em segundos depende de linguagem, compilador, arquitetura, cache, sistema operacional e padrão de entrada. Por isso, a análise teórica costuma abstrair esses detalhes e modelar o custo por número de operações elementares. Chama-se operação elementar uma ação básica do modelo adotado, como comparação, atribuição, acesso a posição de vetor, soma ou teste lógico. Em vez de escrever diretamente o tempo físico $t$, usamos com frequência uma função de custo como $T(n)$, onde $n$ representa o tamanho da entrada.

Essa função pode assumir vários comportamentos típicos:

• constante: $T(n)=c$, quando o custo não depende do tamanho da entrada;
• linear: $T(n)=an+b$, comum em percursos simples;
• quadrática: $T(n)=an^2+bn+c$, frequente em laços duplos;
• logarítmica: $T(n)=a\log n+b$, típica de algoritmos que reduzem o problema por fator constante;
• exponencial: $T(n)=a\cdot 2^n$, frequentemente inviável para entradas grandes.

No caso do espaço, também analisamos como a memória cresce com $n$. Devemos considerar estruturas auxiliares, variáveis temporárias, pilha de chamadas e eventuais tabelas ou buffers adicionais. A pilha de chamadas é a região de memória usada para registrar chamadas de função, parâmetros, endereços de retorno e variáveis locais em execuções recursivas ou aninhadas. Um algoritmo que ordena um vetor no próprio lugar pode usar pouco espaço extra; outro que cria cópias auxiliares pode gastar mais memória em troca de melhor organização ou de uma implementação mais simples.

Outro ponto importante é o critério de caso analisado. Um algoritmo pode apresentar melhor caso, caso médio e pior caso. O melhor caso descreve uma entrada particularmente favorável; o pior caso descreve a situação mais custosa dentro do conjunto de entradas válidas; e o caso médio procura modelar um comportamento esperado segundo alguma distribuição de entradas. Em ordenação por inserção, por exemplo, uma entrada já ordenada tende a ser tratada muito rapidamente, enquanto uma entrada em ordem inversa produz mais deslocamentos. Em muitos contextos teóricos e de engenharia, o pior caso é especialmente relevante porque fornece uma garantia superior para qualquer entrada admissível.

A análise assintótica estuda o comportamento de $T(n)$ quando $n \rightarrow \infty$. Nesse regime, constantes multiplicativas e termos de ordem inferior passam a ter menos importância do que o termo dominante. Assim, funções como

$$ 3n^2 + 5n + 7 $$

e

$$ 100n^2 - 4n + 12 $$

têm a mesma ordem assintótica quadrática, embora em entradas pequenas possam se comportar de forma diferente.

Esse tipo de simplificação é muito útil, mas não deve ser interpretado como desprezo total pelos detalhes. Quando dois algoritmos têm a mesma ordem assintótica, fatores constantes, localidade de memória, paralelismo, custo de E/S e distribuição das entradas ainda podem fazer diferença. A análise assintótica organiza o crescimento de longo prazo, sem substituir completamente medição e engenharia de implementação.

Ao falar em limites de complexidade, distinguimos principalmente cotas superiores e inferiores. Uma cota superior descreve um teto para o custo de um algoritmo conhecido. Se dizemos que uma multiplicação ingênua de matrizes quadradas custa $O(n^3)$, estamos afirmando que seu crescimento não ultrapassa uma constante vezes $n^3$ para entradas suficientemente grandes. Se novos algoritmos melhores forem descobertos, essa cota superior para o problema pode diminuir.

Já uma cota inferior expressa que qualquer algoritmo para certo problema precisa executar pelo menos uma certa quantidade de trabalho em algum modelo de computação. Em vários problemas, a própria leitura da entrada já impõe um custo mínimo. Se um problema recebe $n^2$ dados como entrada, dificilmente fará sentido esperar tempo melhor que $\Omega(n^2)$, pois só inspecionar a entrada já exige essa ordem de operações.

Quando a melhor cota superior conhecida coincide, assintoticamente, com uma cota inferior provada, dizemos que o problema ou algoritmo está assintoticamente ajustado naquele limite. Nesses casos, a solução é frequentemente chamada de assintoticamente ótima, porque não há espaço para melhora de ordem de grandeza dentro do modelo adotado.

As técnicas de prova de cotas inferiores variam conforme o problema. Algumas das mais comuns são:

• argumento de leitura da entrada, quando o próprio tamanho dos dados já impõe trabalho mínimo;
• contagem de estados ou decisões, muito usada em árvores de decisão para ordenação por comparação;
• reduções, mostrando que resolver um problema eficientemente implicaria resolver outro problema já conhecido com certo custo mínimo;
• argumentos adversariais, em que imaginamos uma entrada escolhida para forçar o algoritmo a realizar mais trabalho.

Um exemplo clássico aparece na ordenação por comparações. Nessa família de algoritmos, a única forma permitida de extrair informação relevante é comparar pares de elementos, como em mergesort, heapsort e quicksort em sua formulação clássica por comparação. Existem $n!$ permutações possíveis de uma entrada com $n$ elementos distintos. Cada comparação binária em uma árvore de decisão divide o conjunto de possibilidades, mas para distinguir corretamente todas as permutações a árvore precisa ter pelo menos $n!$ folhas. Isso leva a uma profundidade mínima da ordem de

$$ \log_2(n!) = \Theta(n \log n), $$

o que mostra que algoritmos de comparação não podem, no pior caso, ordenar arbitrariamente mais rápido do que $\Omega(n\log n)$.

A noção de complexidade também depende do modelo computacional adotado. Em teoria da computação, máquinas de Turing são usadas para formalizar algoritmos e custos. Uma máquina de Turing de única fita é mais simples e tende a produzir estimativas mais conservadoras; versões multifita podem simular alguns processos com mais eficiência; versões não determinísticas são úteis para definir classes de complexidade e estudar limites teóricos. Em análise de algoritmos mais próxima da prática, também são comuns modelos como RAM, abreviação de Random Access Machine, em que operações elementares sobre palavras de máquina têm custo unitário e o acesso à memória é tratado como direto.

Esses modelos não servem apenas para formalismo abstrato. Eles deixam explícito que uma afirmação de complexidade sempre depende de hipóteses sobre o que conta como operação básica, como a memória pode ser acessada e quais recursos são permitidos. Ao longo do capítulo, essa base será refinada pelas notações assintóticas formais e pelos métodos de análise de algoritmos iterativos e recursivos.

As notações assintóticas servem para descrever o crescimento de funções de custo quando a entrada se torna grande. Em vez de registrar o tempo exato em segundos, escrevemos como $T(n)$ se comporta em relação a uma função de referência $f(n)$. Assim, expressões como $O(f(n))$, $\Omega(f(n))$ e $\Theta(f(n))$ não representam um único valor, mas classes de funções com certo comportamento de crescimento.

Comecemos com um exemplo simples de código com dois laços aninhados:

operacoes = 0
for i in range(n):
    for j in range(n):
        operacoes += 1

O laço externo executa $n$ vezes. Para cada valor de i, o laço interno também executa $n$ vezes. Portanto, o número total de iterações é:

$$ n \cdot n = n^2 $$

Se cada iteração realiza uma quantidade constante de trabalho, então o custo total cresce quadraticamente. Mesmo que o custo exato fosse algo como

$$ T(n)=2n^2+3n+1, $$

continuaríamos classificando esse algoritmo como quadrático, porque o termo dominante é $n^2$.

A notação Big O, escrita de forma geral como $O(f(n))$, representa um limite superior assintótico. Intuitivamente, dizer que $T(n) \in O(f(n))$ significa que, a partir de certo ponto, a função $T(n)$ não cresce mais rápido do que uma constante vezes $f(n)$. Formalmente:

$$ T(n) \in O(f(n)) $$

se existem constantes $c > 0$ e $n_0$ tais que

$$ T(n) \leq c\cdot f(n), \quad \forall n \geq n_0. $$

Por exemplo, para mostrar que

$$ 3n + 2 \in O(n), $$

basta observar que, para $n \geq 2$, temos

$$ 3n + 2 \leq 4n. $$

Nesse caso, podemos escolher $c=4$ e $n_0=2$.

Já a notação $\Omega(f(n))$ representa um limite inferior assintótico. Ela afirma que a função cresce pelo menos tão rápido quanto uma constante positiva vezes $f(n)$ a partir de certo ponto. Formalmente,

$$ T(n) \in \Omega(f(n)) $$

se existem constantes $c > 0$ e $n_0$ tais que

$$ T(n) \geq c\cdot f(n), \quad \forall n \geq n_0. $$

Por exemplo,

$$ n^2 \in \Omega(n \log n), $$

porque $n^2$ cresce mais rapidamente do que $n \log n$.

A notação $\Theta(f(n))$ é usada quando temos simultaneamente uma cota superior e uma cota inferior da mesma ordem. Em outras palavras, ela descreve crescimento assintoticamente ajustado. Formalmente,

$$ T(n) \in \Theta(f(n)) $$

quando existem constantes positivas $c_1$, $c_2$ e $n_0$ tais que

$$ c_1f(n) \leq T(n) \leq c_2f(n), \quad \forall n \geq n_0. $$

Assim, se

$$ T(n)=5n^2+n+4, $$

podemos escrever que

$$ T(n) \in \Theta(n^2). $$

Esse ponto merece atenção: $O(f(n))$ não significa necessariamente igualdade de ordem, apenas uma cota superior. Por isso, toda função em $\Theta(n)$ também está em $O(n)$, mas uma função em $O(n^2)$ pode na verdade ser linear, logarítmica ou constante. A notação $\Theta$ é mais precisa quando queremos afirmar que duas funções têm essencialmente a mesma taxa de crescimento.

A notação $o(f(n))$, chamada little o, descreve crescimento estritamente menor. Dizemos que

$$ T(n) \in o(f(n)) $$

quando

$$ \lim_{n\to\infty}\frac{T(n)}{f(n)} = 0. $$

Um exemplo simples é:

$$ n \in o(n^2), $$

pois

$$ \frac{n}{n^2} = \frac{1}{n} \to 0. $$

Isso mostra que $n$ cresce estritamente mais devagar do que $n^2$.

Alguns exemplos úteis de classificação são:

• $3n+2 \in O(n)$;
• $5n^2+n+4 \in \Theta(n^2)$;
• $n \log n \in o(n^2)$;
• $n^2 \in \Omega(n \log n)$.

Em análise de algoritmos, algumas ordens de crescimento aparecem com frequência:

• $O(1)$: acesso direto a posição de vetor ou consulta de valor já conhecido;
• $O(\log n)$: busca binária e vários algoritmos que reduzem o problema por fator constante;
• $O(n)$: busca linear, contagem simples e percursos de vetor;
• $O(n \log n)$: mergesort, heapsort e vários algoritmos eficientes de divisão e conquista;
• $O(n^2)$: comparações de todos os pares, bubble sort e insertion sort no pior caso;
• $O(n^3)$: certas rotinas matriciais ingênuas e laços triplamente aninhados;
• $O(2^n)$ e $O(n!)$: algoritmos exponenciais ou fatoriais, comuns em busca exaustiva e enumeração combinatória.

Essas notações não devem ser interpretadas como previsão exata do tempo real de execução. Elas resumem tendências de crescimento e permitem comparar algoritmos em um nível mais abstrato. Dois algoritmos ambos em $O(n \log n)$ podem ter desempenhos bem diferentes na prática, mas a notação continua sendo extremamente útil para separar soluções viáveis de soluções que escalam mal.

Além da análise teórica, também podemos estudar algoritmos por observação direta de seu comportamento em execução. Esse procedimento é chamado de análise empírica ou experimental de performance. A ideia central é executar o programa para diferentes entradas, medir grandezas de interesse e verificar como elas variam com o tamanho do problema. Em vez de deduzir o custo apenas por raciocínio matemático, observamos o algoritmo em uma máquina concreta, com uma linguagem, compilador, sistema operacional e arquitetura específicos.

Esse tipo de medição é muito útil, mas deve ser interpretado corretamente. A análise teórica mostra tendência de crescimento em um modelo abstrato; a análise empírica mostra desempenho observado em um ambiente real. Uma não substitui a outra. A primeira ajuda a generalizar; a segunda ajuda a validar, comparar implementações e detectar gargalos concretos.

Antes de medir qualquer coisa, é preciso definir o que significa o tamanho da entrada. Em um vetor, pode ser o número de elementos. Em um problema sobre grafos, talvez o mais importante seja considerar número de vértices e número de arestas. Em multiplicação de matrizes, a dimensão da matriz é um candidato natural. Em processamento de texto, pode ser o número de caracteres ou palavras. Sem definir claramente o parâmetro de entrada, a medição perde valor interpretativo.

Também é necessário decidir o que será medido. As grandezas mais comuns são:

• tempo total de execução;
• uso de memória;
• número de comparações, trocas ou chamadas, quando o código é instrumentado;
• acessos a disco, rede ou outras operações de E/S;
• eventos de hardware, como falhas de cache, quando há ferramentas apropriadas.

O desenho experimental é parte essencial da análise empírica. Não basta executar uma vez e anotar o resultado. É preciso escolher tamanhos de entrada, construir ou gerar instâncias representativas, repetir execuções, controlar variáveis externas e registrar o ambiente de teste. Em muitos algoritmos, entradas já ordenadas, aleatórias, invertidas ou com muitos valores repetidos podem produzir comportamentos bastante diferentes.

Uma medição isolada costuma ser pouco confiável. Há ruído vindo de cache, escalonamento do sistema operacional, frequência dinâmica da CPU, otimizações do compilador, coleta de lixo em linguagens gerenciadas, JIT, concorrência com outros processos e até aquecimento térmico da máquina. Por isso, é comum executar o mesmo experimento várias vezes e analisar média, mediana, dispersão e possíveis outliers.

Também convém distinguir benchmark e microbenchmark. Um microbenchmark mede um trecho pequeno e bem isolado, como uma operação de busca em vetor ou uma função de ordenação sobre dados já na memória. Um benchmark mais amplo tenta reproduzir cenários de uso real, incluindo carregamento de dados, alocação, E/S, serialização e interação com outras partes do sistema. Ambos são úteis, mas respondem perguntas diferentes.

Um experimento simples pode consistir em executar busca linear e busca binária para vários valores de $n$, registrando o tempo gasto em cada caso. Para cada tamanho de entrada, podemos gerar um vetor, repetir a busca várias vezes e armazenar pares da forma

$$ (n, t) $$

onde $n$ é o tamanho da entrada e $t$ é o tempo observado. Em seguida, podemos comparar se os dados parecem mais compatíveis com crescimento linear, logarítmico, quadrático ou outro padrão.

Um pseudocódigo simples de medição poderia ser:

para cada n em [100, 1000, 10000, 100000]:
    entrada = gerar_dados(n)
    tempos = []
    repetir 30 vezes:
        inicio = relogio()
        algoritmo(entrada)
        fim = relogio()
        tempos.append(fim - inicio)
    registrar(n, media(tempos), mediana(tempos))

Esse tipo de estrutura permite reduzir o efeito de variações ocasionais e produzir uma tabela ou gráfico mais estável. Em muitos estudos, os resultados são visualizados em gráficos lineares, logarítmicos ou log-log, às vezes com barras de erro para representar dispersão.

Ao ajustar uma curva aos dados experimentais, é preciso ter cautela. Um algoritmo pode parecer linear em um intervalo pequeno e depois revelar comportamento quadrático para entradas maiores. Em outro caso, constantes elevadas podem mascarar uma ordem assintótica melhor em tamanhos modestos. Isso mostra por que inferir complexidade apenas por poucos pontos experimentais pode levar a conclusões erradas.

Medir apenas tempo também nem sempre é suficiente. Dois algoritmos podem ter tempos parecidos, mas um deles consome muito mais memória, gera mais alocações, acessa mais disco ou pressiona mais o cache. Em aplicações reais, a escolha de uma solução depende frequentemente de múltiplas métricas, não apenas do menor tempo bruto.

Outro recurso importante é o profiling. Em vez de medir apenas o tempo total, ferramentas de perfil ajudam a descobrir em quais funções, laços ou chamadas o programa realmente gasta mais tempo. Isso evita otimizações cegas e direciona esforço para os pontos mais caros da implementação.

Na engenharia de software, medidas empíricas aparecem em benchmark de bibliotecas, avaliação de estruturas de dados, regressão de performance, comparação entre compiladores, ajuste de consultas em bancos de dados e análise de serviços sob carga. Mesmo quando a complexidade teórica é conhecida, a medição experimental continua essencial para saber se uma implementação concreta está se comportando como esperado.

Essas observações também preparam o terreno para algoritmos recursivos, nos quais o custo nem sempre é evidente pela simples leitura do código. Em muitos casos, experimentação e modelagem por recorrências aparecem lado a lado para explicar o comportamento real do algoritmo.

Quando um algoritmo é recursivo, ele resolve uma instância do problema chamando a si mesmo sobre instâncias menores. Nesses casos, o custo total nem sempre fica evidente apenas olhando o código. Uma forma natural de modelar esse comportamento é por meio de uma recorrência, isto é, uma equação que define o custo atual em função do custo de subproblemas menores.

É importante distinguir dois conceitos próximos, mas diferentes. Recursão é a técnica de implementação em que uma função chama a si mesma. Recorrência é a ferramenta matemática usada para descrever quantitativamente essa execução. A primeira vive no código; a segunda vive na análise.

Uma analogia útil é pensar em subir uma escada resolvendo um degrau por vez. Para chegar ao degrau atual, precisamos já ter resolvido o degrau anterior, somando ainda um pequeno esforço local. Em muitos algoritmos recursivos ocorre exatamente isso: o custo do problema de tamanho $n$ depende do custo do problema de tamanho menor mais algum trabalho adicional feito na chamada atual.

Considere o cálculo recursivo do fatorial:

fatorial(n):
    se n == 0:
        retorna 1
    senao:
        retorna n * fatorial(n - 1)

Se quisermos analisar o custo dessa função, podemos escrever a recorrência

$$ T(n)=T(n-1)+c,\quad T(0)=c_0, $$

em que $c$ representa o trabalho constante feito na chamada atual, como testar o caso base, realizar uma multiplicação e preparar a chamada seguinte. A condição inicial, como $T(0)=c_0$, é indispensável: sem um caso base, a recorrência fica incompleta.

Uma forma intuitiva de resolver essa recorrência é expandi-la passo a passo:

$$ T(n)=T(n-1)+c $$ $$ T(n)=T(n-2)+2c $$ $$ T(n)=T(n-3)+3c $$

Continuando esse processo até chegar ao caso base, obtemos

$$ T(n)=T(0)+nc, $$

o que mostra que o custo cresce linearmente, isto é,

$$ T(n)=\Theta(n). $$

Esse tipo de expansão ajuda a entender a ideia central: cada chamada recursiva adiciona um pequeno custo local, e o número total de chamadas determina a ordem de crescimento. Em problemas mais simples, esse raciocínio já basta para obter a complexidade.

Também é importante separar recorrência de valor e recorrência de custo. Na sequência de Fibonacci, por exemplo, a definição dos valores é:

$$ F(n)=F(n-1)+F(n-2), \quad F(0)=0,\quad F(1)=1. $$

Essa recorrência define os números da sequência. Já o custo do algoritmo recursivo ingênuo para calcular Fibonacci é outro problema. Como cada chamada gera duas subchamadas, a recorrência do custo tem outra forma, ligada ao número de chamadas produzidas.

Podemos ilustrar isso pela árvore de chamadas de fib(5):

fib(5)
├── fib(4)
│   ├── fib(3)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

A árvore deixa visível que certos subproblemas, como fib(3) e fib(2), são recalculados várias vezes. Esse é um dos motivos pelos quais a versão recursiva ingênua de Fibonacci cresce rapidamente. A recorrência de custo pode ser escrita de modo simplificado como

$$ T(n)=T(n-1)+T(n-2)+c, $$

o que produz crescimento exponencial.

Em algoritmos de divisão e conquista, a estrutura da recorrência costuma ser diferente. Na busca binária, por exemplo, cada chamada reduz o problema à metade e faz apenas trabalho constante fora da recursão:

$$ T(n)=T(n/2)+c. $$

Já em mergesort, o vetor é dividido em duas metades, cada metade é ordenada recursivamente, e depois há um custo linear para intercalar os resultados:

$$ T(n)=2T(n/2)+cn. $$

O termo fora da recursão, aqui representado por $cn$, é o trabalho adicional da chamada atual: dividir os dados, combinar resultados, copiar elementos, comparar itens ou organizar estruturas auxiliares.

De forma mais geral, recorrências de análise de algoritmos aparecem com padrões como:

$$ T(n)=T(n-1)+f(n) $$

ou

$$ T(n)=aT(n/b)+f(n), $$

em que $a$ indica quantos subproblemas são gerados, $n/b$ indica o tamanho relativo de cada subproblema e $f(n)$ representa o custo adicional fora das chamadas recursivas.

Há várias técnicas para resolver ou estimar recorrências. As mais comuns neste contexto são:

• expansão ou substituição iterada, abrindo a recorrência passo a passo;
• árvore de recorrência, somando o custo de cada nível da decomposição;
• equações características, especialmente úteis para recorrências lineares em sequências como Fibonacci;
• teoremas gerais, como o Teorema Mestre, para certos casos de divisão e conquista;
• ferramentas algébricas e sistemas simbólicos, quando a manipulação manual se torna trabalhosa.

As equações características aparecem mais naturalmente quando lidamos com recorrências lineares de sequências, não necessariamente com custo de algoritmos. No caso de Fibonacci, por exemplo, ao procurar soluções da forma $x^n$, obtemos a equação

$$ x^2-x-1=0, $$

cujas raízes ajudam a construir a fórmula fechada da sequência. Esse método é útil, mas costuma ser mais apropriado para sequências matemáticas do que para recorrências de custo com divisão e conquista.

Já a árvore de recorrência é uma das ferramentas mais intuitivas. Cada nó representa uma chamada recursiva; os filhos representam os subproblemas gerados; e o custo total pode ser estimado somando o trabalho de todos os níveis. Em mergesort, por exemplo, cada nível da árvore custa aproximadamente $n$, e como há cerca de $\log n$ níveis, o custo total fica em torno de $n\log n$.

O valor prático das recorrências está em permitir que o comportamento de algoritmos recursivos seja previsto antes mesmo da implementação final ou de medições extensas. Elas conectam o código à matemática e ajudam a explicar por que certos algoritmos escalam bem, enquanto outros explodem rapidamente com o aumento da entrada.

Iteração e recursão são duas formas de estruturar algoritmos. Na iteração, repetimos explicitamente um bloco de passos usando estruturas como for e while. Na recursão, a função delega o problema a subinstâncias menores de si mesma até alcançar um caso base. Muitas vezes, ambas as abordagens podem resolver o mesmo problema; em outros casos, a estrutura do próprio problema torna uma delas mais natural.

Uma analogia simples ajuda a visualizar a diferença. A iteração se parece com seguir uma receita linha por linha, usando um único caderno para atualizar o estado do processo. A recursão se parece com empilhar tarefas pendentes: cada chamada deixa uma parte do trabalho em espera, resolve uma versão menor do problema e só depois retorna para concluir o que ficou aberto.

Essa diferença estrutural afeta principalmente o uso de memória. Como vimos na seção anterior com o exemplo do fatorial, cada chamada recursiva empilha um novo quadro de ativação com parâmetros, variáveis locais e endereço de retorno. Por isso, algoritmos recursivos frequentemente consomem memória adicional proporcional à profundidade máxima das chamadas ativas. Isso não significa que a recursão seja sempre pior do que a iteração, mas sim que ela introduz um custo de pilha que precisa ser considerado.

Em problemas simples como o fatorial, a diferença aparece com clareza: a versão iterativa pode manter poucas variáveis e usar espaço auxiliar $O(1)$, enquanto a versão recursiva mantém uma cadeia de chamadas pendentes e usa espaço proporcional à profundidade, tipicamente $O(n)$.

Isso não significa, porém, que toda solução recursiva seja necessariamente inferior. Em árvores, percursos em profundidade, algoritmos de divisão e conquista, parsing e backtracking, a recursão muitas vezes expressa a estrutura do problema com mais clareza. Em alguns cenários, o ganho de legibilidade e de proximidade com a definição matemática compensa o overhead adicional.

Também existem diferentes estilos de recursão. Na recursão linear, cada chamada gera no máximo uma nova chamada relevante, como no fatorial. Na recursão ramificada, uma chamada pode gerar várias outras, como no Fibonacci recursivo ingênuo. Nesse segundo caso, o problema não é apenas a pilha, mas também a repetição maciça de subproblemas já resolvidos.

Considere a versão ingênua de Fibonacci:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

Nessa formulação, valores como fib(3), fib(2) e fib(1) são recalculados muitas vezes. O problema principal não é uma multiplicação em cadeia, mas a recomputação redundante de subproblemas sobrepostos. É justamente aqui que entram memoization e programação dinâmica.

Memoization é uma estratégia top-down: mantemos a formulação recursiva, mas armazenamos resultados já calculados para reutilizá-los em chamadas futuras. Um exemplo simples seria:

memo = {}

def fib_memo(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

Com isso, cada valor de Fibonacci é calculado uma única vez. O custo cai drasticamente em comparação com a versão ingênua.

Outra abordagem é a programação dinâmica bottom-up. Em vez de partir do problema maior e descer recursivamente, resolvemos primeiro os subproblemas menores e construímos a resposta iterativamente:

def fib_bottom_up(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

Nesse caso, a solução usa iteração e evita tanto a árvore exponencial de chamadas quanto a pilha recursiva profunda. Dependendo da formulação, memoization e bottom-up podem transformar uma solução impraticável em uma solução eficiente. O ponto importante é que a melhora vem de evitar recomputação, não de uma regra universal do tipo “toda recursão vira tempo constante”.

Também vale mencionar recursão em cauda, em que a chamada recursiva é a última operação relevante da função. Algumas linguagens ou compiladores conseguem otimizar esse padrão e reutilizar quadros de pilha, mas isso não é garantido em todos os ambientes. Portanto, não se deve assumir automaticamente que uma implementação recursiva será otimizada dessa forma.

Outro risco prático da recursão é o stack overflow. Se a profundidade das chamadas crescer demais e o caso base demorar a ser alcançado, a pilha de execução pode se esgotar. Esse problema aparece tanto por entradas muito grandes quanto por erros de implementação, como casos base incorretos ou chamadas que não reduzem adequadamente o problema.

Na prática, a escolha entre iteração e recursão depende da estrutura do problema, da clareza da solução, das restrições de memória, da profundidade esperada das chamadas e da possibilidade de reaproveitar subproblemas. Em percursos de árvores, divide and conquer e backtracking, a recursão costuma ser muito natural. Em laços simples, acumulações lineares e rotinas com espaço estrito, uma formulação iterativa frequentemente é mais direta e econômica.

Glossário

Algoritmo assintoticamente ótimo

Algoritmo cuja ordem de crescimento coincide com uma cota inferior conhecida para o problema no modelo adotado.

Benchmark

Experimento de medição de desempenho realizado para comparar algoritmos, implementações ou sistemas.

Bottom-up

Estratégia que resolve primeiro subproblemas menores e monta iterativamente a solução do problema maior.

Caso base

Condição de parada de uma função recursiva ou condição inicial de uma recorrência.

Cota inferior

Limite que expressa o mínimo crescimento necessário de custo para um algoritmo ou problema.

Cota superior

Limite que expressa um teto assintótico para o crescimento do custo.

Divisão e conquista

Paradigma em que o problema é dividido em subproblemas menores, resolvidos recursivamente e depois combinados.

Memoization

Técnica de armazenar resultados já calculados para evitar recomputação em chamadas futuras.

Microbenchmark

Medição de desempenho focada em um trecho pequeno e isolado de código.

Modelo RAM

Modelo abstrato em que operações elementares e acessos à memória têm custo unitário.

Operação elementar

Ação básica contada na análise teórica, como comparação, atribuição, soma ou acesso a vetor.

Overhead

Custo adicional de execução que não corresponde diretamente ao trabalho principal do algoritmo.

Pilha de chamadas

Estrutura de memória que guarda o contexto das funções ativas durante a execução.

Profiling

Uso de ferramentas para identificar onde um programa consome mais tempo ou recursos.

Recorrência

Equação que define uma função ou sequência em termos de valores anteriores ou de subproblemas menores.

Recursão

Técnica de programação em que uma função chama a si mesma sobre instâncias menores do problema.

Subproblemas sobrepostos

Subproblemas que reaparecem várias vezes em uma decomposição recursiva, permitindo reaproveitamento de resultados.

Teorema Mestre

Ferramenta para estimar recorrências de divisão e conquista de certas formas padronizadas.

Top-down

Estratégia que parte do problema maior e o reduz recursivamente a subproblemas menores.

Referências:

1. Complexidade de algoritmos - Siang Wun Song
2. Análise de Algoritmos Recursivos
3. Recursion - Christopher M. Bourke - Nebraska-Lincoln School Of Computing

< 7 - Probabilidade e Estatística > 9 - Algoritmos e Estruturas de Dados