®

Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 1

Capítulo 2
Análise Assintótica da
Complexidade de Algoritmos

“Aconselho os meus alunos a terem muito cuidado quando decidirem não estudar
mais Matemática. Nesse momento, eles devem estar preparados para ouvirem
o som de portas se fechando.” -- James Caballero

1. Complexidade assintótica: O, Omega e Theta

Ao ver uma expressão como n+10 ou n2+1, a maioria das pessoas pensa
automaticamente em valores pequenos de n, valores próximos de zero. A análise
de algoritmos faz exatamente o contrário: ignora os valores pequenos e
concentra-se nos valores enormes de n. Para valores enormes de n, as funções

n2 , (3/2)n2 , 9999n2 , n2/1000 , n2+100n , etc.

crescem todas com a mesma velocidade e portanto são todas "equivalentes".

Esse tipo de análise, interessado somente em valores enormes de n, é chamado
assintótica. Nessa matemática, as funções são classificadas em "ordens"; todas
as funções de uma mesma ordem são "equivalentes". As cinco funções acima, por
exemplo, pertencem à mesma ordem.

Ordem O (‘big O’, ‘O grande’)

Convém restringir a atenção a funções assintoticamente não-negativas, ou seja,
funções f tais que f(n) ≥ 0 para todo n suficientemente grande. Mais
explicitamente: f é assintoticamente não-negativa se existe n0 tal que f(n) ≥ 0
para todo n ≥ n0. Agora podemos definir a ordem O.
DEFINIÇÃO: Dadas funções assintoticamente não-negativas f e g, dizemos que f
está na ordem O de g, e escrevemos f = O(g) ou f ∈ O (g), se f(n) ≤
c · g(n) para algum c positivo e para todo n suficientemente grande. Em
outras palavras, existe um número positivo c e um número positivo n0 tais que
f(n) ≤ c · g(n) para todo n ≥ n0. Neste caso, dizemos que g(n) domina
assintoticamente f(n), ou que g(n) é um limite assintótico superior para f(n). A
Figura 1 apresenta um exemplo gráfico da notação O:
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 2

c g(n)

f(n) = O(g(n))

f(n)

n
no

Figura 1 - A notação O dá um limite superior para a função f(n). Dizemos que

f(n) é O(g(n)) se existem constantes positivas c e n0, de forma que à direita de
n0, o valor de f(n) está sempre abaixo ou igual a c.g(n).

EXEMPLO: Suponha que f(n) = (3/2)n2 + (7/2)n - 4 e que g(n) = n2. A tabela
abaixo sugere que f(n) ≤ 2g(n) para n ≥ 6 e, portanto, parece que f(n) =
O(g(n)).
n f(n) g(n)
0 -4 0
1 1 1
2 9 4
3 20 9
4 34 16
5 51 25
6 71 36
7 94 49
8 120 64
É fácil verificar que, de fato, f(n) = O(g(n)) com um cálculo mais
grosseiro: f(n) ≤ 2n2+4n2 = 6n2 = 6g(n) para todo n.

Uma outra forma de verificar se uma função g(n) domina assintoticamente

uma outra função f(n) é a seguinte:

f ( n)
Se 0 ≤ lim < ∞ , f(n) = O(g(n)).
n − >∞ g ( n)

Teorema: Se A(n)=Amnm + ... + A1n + A0 é um polinômio de grau m, então A(n)

é O(nm).
Exemplo: A função de complexidade de um algoritmo A é dada por
f(n)=n3+2n2+n+1. Logo, podemos dizer que este algoritmo tem complexidade
O(n3). Isto significa que para valores muito grandes de n, poderíamos
desconsiderar a outra parte do polinômio (2n2+n+1), pois ela não influenciaria
tanto no crescimento de f(n).
Ordem o (o pequeno)
DEFINIÇÃO: Dadas funções assintoticamente não-negativas f e g, dizemos que f
está na ordem o de g, e escrevemos f = o(g) ou f ∈ o (g), se f(n) < c ·
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 3

g(n) para algum c positivo e para todo n suficientemente grande. Em outras

palavras, existe um número positivo c e um número positivo n0 tais que f(n) <
c · g(n) para todo n ≥ n0.

Intuitivamente, dizemos que “o pequeno” é assintoticamente análogo a

“menor que” e “O grande”, análogo a “menor ou igual a”. Assim, 2n2 é O(n2),
mas não é o(n2). Já 2n é o(n2) e O(n2).

Algumas propriedades da função O

(i) f(n) = O(f(n))
(ii) c.O(f(n)) = O(f(n)), c constante
(iii) O(f(n)) + O(f(n)) = O(f(n))
(iv) O(O(f(n)) = O(f(n))
(v) O(f(n)) + O(g(n)) = O(Max(f(n), g(n)))
(vi) O(f(n)). O(g(n)) = O(f(n).g(n))
(vii) O(f(n).g(n)) = f(n) . O(g(n))

Ordem Ω (Omega)
A expressão "f = O(g)" tem o significado matemático de "f ≤ g". Agora
precisamos de um conceito que tenha o significado de "f ≥ g".
DEFINIÇÃO: Dadas funções assintoticamente não-negativas f e g, dizemos que f
está na ordem Omega de g, e escrevemos f = Ω(g), ou f ∈ Ω(g), se f(n)
≥ c · g(n) para algum c positivo e para todo n suficientemente grande. Em
outras palavras, existe um número positivo c e um número positivo n0 tais que
f(n) ≥ c · g(n) para todo n ≥ n0. Neste caso, dizemos que g(n) é um limite
assintótico inferior para f(n). Na Figura 2 a seguir, a notação Ω é apresentada
graficamente.

f(n)
f(n) = Ω(g(n))

c g(n)

n
no

Figura 2 - A notação Ω dá um limite inferior para a função f(n). Dizemos que f(n)
é Ω(g(n)) se existem constantes positivas c e n0, de forma que à direita de n0, o
valor de f(n) está sempre acima ou igual a c.g(n).

EXEMPLO: Se f(n) ≥ g(n)/100000 para todo n ≥ 888 então f = Ω(g). (Mas

cuidado: a recíproca não é verdadeira!)
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 4

Uma outra forma de verificar se uma função f(n) domina assintoticamente

uma outra função g(n) é a seguinte:

f ( n)
Se 0 < lim ≤ ∞ , f(n) =Ω (g(n)).
n − >∞ g ( n)

Qual a relação entre O e Ω? Não é difícil verificar que f = O(g) se e

somente se g=Ω(f).

Ordem ω

DEFINIÇÃO: Dadas funções assintoticamente não-negativas f e g, dizemos que f

está na ordem ω de g, e escrevemos f = ω(g) ou f ∈ ω(g), se f(n)> c ·
g(n) para algum c positivo e para todo n suficientemente grande. Em outras
palavras, existe um número positivo c e um número positivo n0 tais que f(n) >
c · g(n) para todo n ≥ n0.

Intuitivamente, dizemos que ω é assintoticamente análogo a “maior que” e

Ω análogo a “maior ou igual a”. Assim, n2/2 é Ω(n2), mas não é ω(n2). Já n2/2 é
Ω(n) e ω(n).

Ordem Θ (Theta)
Além dos conceitos de "f ≤ g" e de "f ≥ g", precisamos de um que tenha o
significado de "f = g".
DEFINIÇÃO: Dizemos que f e g estão na mesma ordem Theta e escrevemos
f = Θ(g) ou f ∈ Θ(g) se f = O(g) e f = Ω(g). Trocando em miúdos, f
= Θ(g) significa que existem números positivos c1 e c2 tais que c1·g(n) ≤
f(n) ≤ c2·g(n) para todo n suficientemente grande (n ≥ n0). Na Figura 3 a
notação Θ é apresentada graficamente.

c2 g(n)

f(n) = θ(g(n))

f(n)

c1 g(n)

n
no

Figura 3 - Dizemos que f(n) é Θ(g(n)) se existem constantes positivas c1, c2 e

n0, de forma que à direita de n0, o valor de f(n) está sempre entre (inclusive)
c1.g(n) e c2.g(n).
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 5

EXEMPLO: As funções abaixo pertencem todas à ordem Θ(n2):

n2 , (3/2)n2 , 9999n2 , n2/1000 , n2+100n .

Uma outra forma de verificar se uma função f(n)=Θ g(n) é a seguinte:

f ( n)
Se 0 < lim < ∞ , f(n) =Θ (g(n)).
n − >∞ g ( n)

Propriedades de O, Ω e θ
(i) Reflexividade : f(n) = O(f(n)), f(n) = Ω(f(n)), f(n) = Θ(f(n))

(ii) Transitividade:

Se f(n) = O(g(n)) e g(n) = O(h(n)), então f(n) = O(h(n))

Se f(n) = Ω (g(n)) e g(n) = Ω (h(n)), então f(n) = Ω (h(n))

Se f(n) = Θ (g(n)) e g(n) = Θ (h(n)), então f(n) = Θ (h(n))

(iii) f(n) = Θ(g(n)) se e somente se f(n) = O (g(n)) e f(n) = Ω (g(n))

(iv) Simetria: f(n) = Θ(g(n)) se e somente se g(n) = Θ(f(n))

(v) Simetria Transposta

f(n) = O(g(n)) se e somente se g(n) = Ω(f(n))

f(n) = Ω(g(n)) se e somente se g(n) = O(f(n))

Essas propriedades das notações assintótica sugerem uma analogia entre

a comparação assintótica de duas funções f e g e a comparação de dois números
reais a e b:

f(n) = O(g(n)) ≈ a ≤ b,
f(n) = Ω(g(n)) ≈ a ≥ b,
f(n) = Θ(g(n)) ≈ a = b,
f(n) = o(g(n)) ≈ a < b,
f(n) = ω(g(n)) ≈ a > b.

Entretanto, uma propriedade dos números reais não se aplica à notação

assintótica. Tricotomia: Para quaisquer dois números reais a e b, a < b ou a = b
ou or a > b.
Embora quaisquer dois números reais possam ser comparados, nem todas
as funções são assintoticamente comparáveis. Isto é, para duas funções f(n) e
g(n), pode não acontecer f(n) = O(g(n)) nem f(n) = Ω(g(n)). Por exemplo, as
1+ sen n
funções n e n não podem ser comparadas usando notação assintótica, uma
vez que o valor do expoente 1+sen n oscila entre 0 and 2.
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 6

3. Algoritmos e Classes de Comportamento Assintótico

Algoritmos podem ser classificados segundo as suas ordens de complexidade. As
principais classes de comportamento assintótico de algoritmos são as seguintes:
• O (1) : constante – mais rápido, impossível. O uso do algoritmo independe
do tamanho de n. Neste caso as instruções do algoritmo são executadas
um número fixo de vezes.
• O (log n): muito bom, ocorre tipicamente em algoritmos que resolvem um
problema transformando-o em problemas menores.
• O (n): linear – Em geral um pequeno trabalho é realizado sobre cada
elemento de entrada. Esta é a melhor situação possível para um algoritmo
que tem que processar n elementos de entrada ou produzir n elementos
de saída. Cada vez que n dobra de tamanho o tempo de execução dobra.
• O (n log n): limite de muitos problemas práticos, ex.: ordenar uma
coleção de números. Este tempo de execução ocorre tipicamente em
algoritmos que resolvem um problema quebrando-o em problemas
menores, resolvendo cada um deles independentemente e depois
ajuntando as soluções.

• O (n2): quadrático. Algoritmos desta ordem de complexidade ocorrem

quando os itens de dados são processados aos pares, muitas vezes em um
anel (loop) dentro de outro. Algoritmos deste tipo são úteis para resolver
problemas de tamanhos relativamente pequenos.

• O (nk): polinomial – OK para k pequeno.

• O (kn), O (n!), O (nn): exponencial – evite! Algoritmos desta ordem de

complexidade geralmente não são úteis sob o ponto de vista prático. Eles
ocorrem na solução de problemas quando se usa força bruta para
resolvê-los.
Para ilustrar melhor a diferença entre as classes de comportamento
assintótico, vamos observar a Tabela 1 a seguir. Nela é mostrada a razão de
crescimento de várias funções de complexidade para tamanhos diferentes de n,
em que cada função expressa o tempo de execução em microssegundos. Nesta
tabela, um algoritmo linear executa em um segundo um milhão de operações.

Função de n=10 n=20 n=30 n=40 n=50 n=60

custo
n 0,00001 s 0,00002 s 0,00003 s 0,00004 s 0,00005 s 0,00006 s
n2 0,0001 s 0,0004 s 0,0009 s 0,0016 s 0,0025 s 0,0036 s
n3 0,001 s 0,008 s 0,027 s 0,064 s 0,125 s 0,316 s
n5 0,1 s 3,2 s 24,3 s 1,7 min 5,2 min 13 min
2n 0,001 s 1s 17,9 min 12,7 dias 35,7 anos 366 séc.
3n 0,59 s 58 min 6,5 anos 3855 séc. 108 séc. 1013 séc.
Tabela 1 Diferença entre algumas classes de comportamento assintótico
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 7

4. Complexidade e suas cotas

Suponha que A é um algoritmo a ser analisado, In é o conjunto de todas as
possíveis entradas de A, cada uma com tamanho n. Seja fA, uma função que
expressa o custo de A, ou seja, se I é uma entrada em In, fA(I) é o custo de A
para a entrada I. Então:

Pior caso: W(A) = max fA(I)

I ∈ In

Melhor caso: B(A) = min fA(I)

I ∈ In
n
Caso médio: E(A) = ∑ i. p
i =0
i , distribuição de probabilidade, onde pi é a

probabilidade do evento i ocorrer.

Graficamente, podemos representar o pior caso, melhor caso e caso médio

conforme a figura a seguir:

tempo para o pior caso

Tempo de execução

tempo para o caso médio

tempo para o melhor caso

Instância de entrada

Figura 4 – A diferença entre o tempo para o pior caso e o tempo para o melhor
caso. Cada barra representa o tempo de execução de um algoritmo sobre uma
entrada diferente.

Exemplo:

Seja o seguinte trecho de algoritmo:

(1) para i de 1 até n faça

(2) se (A[i] <= x)
(3) A[i] = 2*A[i]

Encontre a função de complexidade f(n) do trecho dado, em relação ao

número de multiplicações realizadas (linha 3), para o melhor caso, o pior
caso e o caso médio. Para o caso médio utilize o conceito de distribuição de
probabilidade.

No melhor caso, a condição da linha (2), A[i] <= x, nunca é satisfeita,

logo f(n)=0.
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 8

No pior caso, a condição da linha (2) é sempre satisfeita, logo f(n)=n,

dado pelo número de vezes que o comando ‘para’ (linha 1) é executado. Logo, no
pior caso, o algoritmo é O(n).

No caso médio, vamos considerar a seguinte distribuição de

probabilidade:

n
1 1 1 1 1 1+ n 1 n
∑i. p
i =0
i = 0.
n +1
+ 1.
n +1
+ 2.
n +1
+ ... + n.
n +1
= (1 + 2 + ... + n).
n +1
=(
2
).n. =
n +1 2

Assim, no caso médio o algoritmo também é O(n), pois n/2 é O(n).

Cota Superior e Cota Inferior de um Problema

Cota Superior de um problema P: é a menor das complexidades de pior caso

dos algoritmos existentes (conhecidos) para resolver P. Indica que podemos
sempre resolver, para instâncias arbitrárias de tamanho n, o problema P, com
tempo menor ou igual à cota superior. Em outras palavras, não devemos ficar
satisfeitos com um algoritmo de complexidade de pior caso maior que a cota
superior, pois um outro algoritmo de complexidade de pior caso igual à cota
superior já existiria. A cota superior é o mínimo sobre todos os algoritmos
existentes.

A cota superior de um problema é parecida com o record mundial de uma

modalidade de atletismo. Ela é estabelecida pelo melhor atleta (algoritmo) do
momento. Assim como o record mundial, a cota superior pode ser melhorada por
um algoritmo (atleta) mais veloz. Na tabela a seguir, temos a cota superior dos
100 metros rasos no atletismo:

Ano Atleta (Algoritmo) Tempo

1988 Carl Lewis 9s92
1993 Linford Christie 9s87
1993 Carl Lewis 9s86
1994 Leroy Burrell 9s84
1996 Donovan Bailey 9s84
1999 Maurice Greene 9s79
2002 Tim Montgomery 9s78
Tabela 2 Cota Superior dos 100 metros rasos

Cota Inferior de um problema P: é a complexidade intrínseca ou inerente de um

problema P. Isto é, nenhum algoritmo pode resolver o problema com
complexidade de pior caso menor que a cota inferior, para entradas arbitrárias de
tamanho n. A cota inferior é o mínimo sobre todos os algoritmos possíveis. Na
analogia anterior, uma cota inferior de uma modalidade de atletismo não
dependeria mais do atleta. Seria algum tempo mínimo que a modalidade exige,
qualquer que seja o atleta. Uma cota inferior trivial para os 100 metros rasos
seria o tempo que a velocidade da luz leva para percorrer 100 metros no vácuo.
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 9

Quando a cota superior de um problema P é igual a sua cota inferior,

dizemos que P tem um algoritmo ótimo que o resolve.

Exemplo:

Suponha que um determinado problema P tem cota inferior igual a n e

cota superior igual a n2.
n2

Faixa de
algoritmos n
aceitáveis

Figura 3 – Entendendo os conceitos de Cota Inferior e Cota Superior

Qualquer algoritmo que resolva P com complexidade de pior caso maior

que n2 (por exemplo, n3, n4) não deveria ser aceito, pois já existe algoritmo O(n2)
que o resolve.

De forma semelhante, também devemos desconfiar de qualquer algoritmo

que diz resolver P com complexidade de pior caso menor que n (por exemplo,
lgn, n1/2), pois essas complexidades estão abaixo da cota inferior n, que
representa um limite inferior para as complexidades dos algoritmos que resolvem
P.

Qualquer algoritmo com complexidade de pior caso entre a cota superior e

a cota inferior (por exemplo, nlgn, n3/2) pode ser aceito.

No caso do problema de ordenação, é sabido que a cota inferior e a cota

superior são iguais a [Link]. Nesse caso, dizemos que o problema de ordenação
tem um algoritmo ótimo que o resolve, pois não tem como esse algoritmo ser
melhor (menor que a cota inferior).

5. Alguns Princípios da Análise de Algoritmos

1. O tempo de execução de um comando de atribuição, de entrada ou de
saída é O(1) ou O(k), k constante.
2. O tempo de execução de uma seqüência de comandos é o maior tempo de
execução de qualquer comando da seqüência. O(f(n)) + O(g(n)) = O(Max
(f(n), g(n)))

Exemplo: Suponha 3 trechos seqüenciais de um programa com tempos de

execução O(n), O(n2) e O(nlogn). O tempo de execução dos 2 primeiros
trechos é O(max(n,n2), que é O(n2). O tempo de execução de todos os 3
trechos é, então, O(max(n2, nlogn)), que é O(n2)
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 10

3. O tempo de execução de um comando de decisão simples é composto

pelo tempo para avaliar a condição mais o tempo dos comandos executados
dentro da condição.

Obs.: comandos if-then-else

if (cond) {
seqüência de comandos 1
}
else {
seqüência de comandos 2
}
Neste caso, será executada a seqüência de comandos 1 ou a seqüência de
comandos 2. Assim, a complexidade de pior caso é dada por Max(seq1,
seq2). Por exemplo, se a seqüência 1 é O(N) e a seqüência 2 é O(1), a
complexidade de pior caso para a declaração inteira do if-then-else é O(N).
4. O tempo para executar um comando de repetição é a soma do tempo de
execução do corpo do laço mais o tempo de avaliar a condição de parada
multiplicado pelo número de iterações do laço.
Ex.: loop FOR
for (i = 0; i < N; i++) {
seqüência de comandos
}
O loop acima é executado N vezes, logo a seqüência de comandos é
executada também N vezes. Assumindo que a seqüência de comandos é
O(1), o tempo total para o loop é N * O(1), ou seja, O(N).
Ex.: loop FOR aninhado
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
seqüência de comandos
}
}

O FOR mais externo executa N vezes. Cada vez que ele é executado, o FOR
mais interno executa M vezes. Como resultado a seqüência de comandos no
FOR mais interno é executa do N*M vezes. Assim, a complexidade é O(N*M).
Se a condição de parada do FOR mais interno fosse N, ao invés de M, a
complexidade do trecho acima seria O(N2), ou seja, complexidade
quadrática.

Outro exemplo de cálculo de complexidade do loop FOR é apresentado a

seguir:

for (i = 2; i <= N-2; i++) {

for (j = 1; j < N+2; j++) {
c1
}
}
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 11

N − 2 N +1
No trecho acima, o comando c1 é executado ∑∑
i=2 j =1
1 vezes, ou seja
N −2

∑ ( N + 1) = ( N + 1)( N − 3) = N
i =2
2
− 2 N − 3 vezes.

Podemos também ter situações com um loop aninhado onde o número de vezes do
loop mais interno depende do valor do índice no loop mais externo, como no trecho a
seguir:

for (i = 0; i < N; i++) {

for (j = i; j < N; j++) {
c1
}
}

N −1 N −1
No trecho acima, o comando c1 é executado ∑∑
i =0 j =i
1 vezes, ou seja
N −1
N2 + N
∑
i =0
( N − i ) = ( N ) + ( N − 1) + ( N − 2) + ... + 1 =
2
vezes.

5. Programas com rotinas não recursivas

(i) Cada rotina é tratada separadamente iniciando por aquelas que não
chamam outra rotina.
(ii) A seguir, computar o tempo das rotinas que chamam as rotinas que não
chamam outras rotinas, utilizando os tempos já avaliados em (i).
(iii) Repetir o processo até chegar na rotina principal.

Obs.: Comandos com chamadas de rotinas:

Quando um comando envolve a chamada de uma rotina, a complexidade

do comando deve incluir a complexidade da rotina chamada. Assuma que
é sabido que uma rotina f tem tempo constante, e uma rotina g tem um
tempo linear proporcional a um parâmetro k. Então, os comandos a seguir
possuem as complexidades indicadas:

f(k); // O(1)
g(k); // O(k)

Quando essas rotinas são chamadas em um loop FOR, por exemplo, as

mesmas regras continuam sendo aplicadas. Por exemplo:

for (j = 0; j < N; j++) g(N);

tem complexidade O(N2). O loop é executado N vezes e cada chamada da

rotina g(N) tem complexidade O(N).

6. Programas com rotinas recursivas

Para analisar uma rotina recursiva é necessário primeiro encontrar uma
relação de recorrência que descreve a rotina. Em seguida, devemos
"resolver" a relação de recorrência. Na próxima seção, veremos com mais
detalhes como encontrar a complexidade de algoritmos recursivos.
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 12

6. Análise de Complexidade de Algoritmos Recursivos

Para analisar um algoritmo recursivo é necessário "resolver" uma relação de
recorrência. Uma relação de recorrência é uma "fórmula" que define uma função
(em geral sobre os números naturais). Por exemplo, eis uma relação de
recorrência que define uma função T nos pontos 1, 2, etc.
T(1) = 1
T(n) = T(n-1) + 3n + 2 para n = 2, 3, 4, etc.

Os valores de T(n) para valores pequenos de n são:

n 12 3 4 5 6 ...
T(n) 1 9 20 34 51 71 ...
Para a relação de recorrência:
T(1) = 2
T(n) = 2T(n-1) para n ≥ 2,
temos:
T(1) = 2
T(2) = 2T(1) = 2 · 2 = 22
T(3) = 2T(2) = 2 · 22 = 23
T(4) = 2T(3) = 2 · 23 = 24
T(5) = 2T(4) = 2 · 24 = 25
Podemos concluir que T(n)=2n. Esta equação é denominada solução em forma
fechada para a relação de recorrência T(n) sujeita à condição básica T(1).
Denomina-se RESOLVER uma relação de recorrência ao processo de se
encontrar uma solução em forma fechada para a recorrência. Sempre que
possível é bom encontrar uma solução em forma fechada para a recorrência.
Resolver recorrências nem sempre é fácil. Existem vários métodos de
resolução de relações de recorrência que são vistos na disciplina CIC111
(Matemática Discreta II). Em CIC210, revisaremos alguns desses métodos,
suficientes para resolver as relações de recorrência da maioria dos algoritmos
recursivos que iremos estudar.

6.1. Método da Iteração

Nem sempre temos intuição suficiente sobre a forma geral da recorrência para
dar um palpite correto. O método da iteração permite que se reconheça um
padrão sem necessidade de chutar ou adivinhar, como fizemos na recorrência
T(n)=2T(n-1). A solução do problema da recorrência é obtida através de
manipulação algébrica da expressão, geralmente resolvendo-se um somatório.
O método da iteração consiste esquematicamente de:
• Algumas iterações do caso geral são expandidas até se encontrar uma lei
de formação.
• O somatório resultante é resolvido substituindo-se os termos recorrentes
por fórmulas envolvendo apenas o(s) caso(s) base.
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 13

Exemplo:
T(n) = 2T(n/2)+n
T(1)=1
Resolvendo esta recorrência pelo método da iteração, temos:
T(n) = 2T(n/2) + n
= 2T(n/4)+n/2)+n = 4T(n/4)+2n
= 4(2T(n/8)+n/4)+2n = 8T(n/8)+3n
= 8(2T(n/16)+n/8)+3n = 16T(n/16)+4n
= ...
= 2kT(n/(2k))+kn
Lembramos que, no limite, temos que chegar no caso base da recursão,
k
ou seja, T(1). Para termos a fórmula acima em termos de T(1), n/(2 ) tem que
k
convergir para 1, e isso só acontece se 2 =n, ou seja, k=lgn. Temos então:
T(n) = 2lgn T(n/2 lgn))+(lgn)n
= nlg2 T(1)+nlgn
= n + nlgn
6.2. Teorema Mestre
Utilizado para resolver recorrências cujo caso geral é da forma T(n) = a.T(n/b) +
f(n), onde a≥1 e b>1 são constantes, n/b significa ⎡n/b⎤ ou ⎣n/b⎦, e f(n) é uma
função assintoticamente positiva.
Podemos interpretar esta relação de recorrência associada a um algoritmo
recursivo como: o algoritmo divide o problema em a partes iguais, cada uma de
tamanho b vezes menor que o problema original. O trabalho executado em cada
instância da recursão é determinado pela função f(n).
O método consiste no teste de três casos, tornando mais simples a solução
de muitas recorrências:

1. Se f(n)=O(n(logba) - ε) para uma constante ε>0,

então T(n)= Θ(nlogba)

2. Se f(n)= Θ(nlogba) para uma constante ε>0,

então T(n)= Θ([Link] n)

3. Se f(n)= Ω(n(logba) + ε) para uma constante ε>0,

e se af(n/b) ≤cf(n), para alguma constante c<1 e n suficientemente grande
então T(n)= Θ(f(n))
Nos 3 casos estamos comparando a função f(n) com a função nlogba . A
solução da recorrência é dada pela maior das duas funções.
• No caso 1, a função nlogba é maior, então a solução é T(n)= Θ (nlogba)
• No caso 3, a função f(n) é maior, então a solução é T(n)= Θ (f(n))
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 14

• No caso 2, as funções são de mesma dimensão, sendo introduzido um

fator lg n e a solução é T(n)= Θ ([Link] n) = Θ (f(n).lg n)
É importante ressaltar que o teorema não cobre todos os casos possíveis.
No caso 1, f(n) deve ser menor que nlogba por um fator polinomial nε, para alguma
constante ε>0. No caso 3, f(n) deve ser maior que nlogba por um fator polinomial
nε, para alguma constante ε>0.
Além disso, para o caso 3, deve também ser satisfeita a condição de
regularidade onde af(n/b) ≤ cf(n), constante c<1.
Exemplo: (usando a mesma relação de recorrência utilizada no método da
iteração)
T(n) = 2T(n/2)+n
T(1)=1
A relação de recorrência se encaixa no caso geral T (n) = a.T(n/b) + f(n), onde
a≥1 e b>1 são constantes e f(n) é uma função assintoticamente positiva.
Na recorrência T(n)=2T(n/2)+n, temos a=2, b=2, f(n)=n
Vamos testar o caso 1 do Teorema Mestre:

1. Se f(n)=O(n(logba) - ε) para uma constante ε>0,

então T(n)= Θ(nlogba)

n=O(n(log22) - ε) para uma constante ε>0?

n=O(n1-ε) para uma constante ε>0? É fácil verificar que não!

Vamos então testar o caso 2 do Teorema Mestre:
2. Se f(n)= Θ(nlogba) para uma constante ε>0,
então T(n)= Θ([Link] n)

n = Θ(nlog22) para uma constante ε>0?

n = Θ(n) para uma constante ε>0? É fácil verificar que sim!
Logo, pela conclusão do caso 2, temos que T(n) = Θ([Link] n) = Θ([Link] n)

6.3. Complexidade de relações-padrão

• T(n)=T(n/c) + k, k,c constantes, c>1, T(n)=O(logcn)
• T(n)=cT(n/c) + k, k,c constantes, c>1, T(n)=O(n)
• T(n)=aT(n/c) + k, k, a, c constantes, a>c, c>1, T(n)=O(nlogca)
• T(n)=aT(n/c) + kn, k, a, c constantes, c>1,
a<c, T(n)=O(n)
a=c, T(n)=O(nlgn)
a>c, T(n)=O(nlogca)
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 15

Exercícios de Fixação
1) Usando a definição da ordem O, demonstre a seguinte propriedade:
O(f(n)) + O(g(n)) = O(Max(f(n), g(n)))
2) Prove que an2 + bn + c = θ (n2), para quaisquer constantes a, b, c e a > 0.

3) Dê um exemplo de duas funções f(n) e g(n), f(n) ≠ g(n), onde f(n) = O(g(n)) e
g(n) = O(f(n)). Justifique.

4) Marque V ou F. Justifique.

Sempre que f=O(h) e g=O(h), f=O(g)

Se f≠g e f=O(g) então g=O(f)

As funções [Link](n) e [Link](n.n) possuem a mesma ordem de complexidade

log(nc) é Θ(log(n)) para qualquer constante c>0

2100 é O(1)

2n-1 = O(2n)

2n = ω(2n-1)

5) Em um futuro próximo, você precisa resolver um determinado problema. João

V. Lozz lhe oferece dois algoritmos, A1 e A2, que resolvem o problema com
funções de complexidade n2+n e 103nlgn, respectivamente. Qual desses algoritmos
você escolheria? Justifique cuidadosamente a sua resposta.

6) Qual o menor valor de n de forma que um algoritmo cujo tempo de execução é

100n2 roda mais rápido que um algoritmo cujo tempo de execução é 2n, rodando
na mesma máquina?

7) Classifique as seguintes funções de acordo com a ordem de crescimento de

cada uma, ou seja, encontre uma ordem g1, g2, g3, ..., g10, de funções que
satisfaçam g1 = Ω(g2), g2 = Ω(g3), g3 = Ω(g4), ..., g9 = Ω(g10).

lg(lg n), n1/2 , n2, n2lgn, nlgn, lg n , nn, n3, 5!, 2lgn

8) João V. Lozz, na análise de quatro algoritmos para criptografia de dados, A1,

A2, A3 e A4, encontrou as seguintes expressões para o número de operações
matemáticas realizadas:
A1: f(n) = log n10 A2: f(n) = n2/3
A3: f(n) = n3/2 A4: f(n) = 4
n

Ajude-o a demonstrar o seguinte:

a) A1 é θ(log n)
b) A2 é o([Link])
c) A3 é ω([Link] n)
d) A4 é Ω(ln2 n)
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 16

9) Marque V ou F. Jusitifique .

Um algoritmo com complexidade O(lgn) é adequado para resolver um

problema cuja cota inferior é n.
Um algoritmo com complexidade O(n3/2) não deveria ser usado para resolver
um problema cuja cota superior é n2 e cota inferior n.
Um algoritmo com complexidade Ω(n3) não deveria ser usado para resolver
um problema cuja cota superior é n3.

10) João V. Lozz diz ter desenvolvido um algoritmo de complexidade O(n2/3) para
ordenar um conjunto de n elementos. Você compraria este algoritmo? Justifique
cuidadosamente a sua resposta. (obs.: sabe-se que a cota inferior e a cota
superior para o problema de ordenação é [Link]).
11) José $á Bido diz ter desenvolvido um algoritmo de complexidade O(n3/2) para
ordenar um conjunto de n elementos. Você compraria este algoritmo? Justifique
cuidadosamente a sua resposta.
12) Considere o algoritmo a seguir para encontrar o maior elemento e o menor
elemento de uma sequência A[1..n], n ≥ 1.

Procedure MaxMin (var A: Vetor; var Max, Min: integer);

var i: integer;
begin
Max := A[1];
Min := A[1];
for i := 2 to n do
begin
if A[i] > Max then Max := A[i];
if A[i] < Min then Min := A[i];
end
end;

Seja C(n) o número de comparações entre os elementos de A. a) Calcule C(n)

para o melhor caso, pior caso e caso médio. b) Proponha um algoritmo mais
eficiente para resolver este problema. c) Calcule C(n) para esse novo algoritmo.
13) Encontre o número de comparações no caso médio para o seguinte trecho
de programa:

for i:= 2 to n do
if A[i] < x then x := A[i];

14) Dado o seguinte trecho do algoritmo:

(1) i := 1;
(2) repetir
(3) se (A[i] <= 10)então x := A[i]
(4) senão se (A[i] <= 100) então y := A[i]
(5) senão se (A[i] <= 1000) então z := A[i];
(6) i := i + 1
(7) até (i > n);

Encontre a função de complexidade C(n), do caso médio, em relação ao

número de comparações realizadas no vetor A.
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 17

15) Encontre a complexidade de cada um dos seguintes trechos de programa:

a) Dois loops em seqüência:

for (i = 0; i < N; i++) {

seqüência de comandos
}
for (j = 0; j < M; j++) {
seqüência de comandos
}
O que acontece se trocarmos a complexidade do segundo loop por N ao invés de
M?

b) Um loop aninhado seguido por um loop não aninhado:

for (i = 0; i < N; i++) {

for (j = 0; j < N; j++) {
seqüência de comandos;
}
}
for (k = 0; k < N; k++) {
seqüência de comandos
}

c) Um loop aninhado onde o número de vezes do loop mais interno depende do

valor do índice no loop mais externo:

for (i = 0; i < N; i++) {

for (j = i; j < N; j++) {
seqüência de comandos
}
}

16) Encontre a complexidade de melhor caso e de pior caso do seguinte trecho

de programa:

if (x==y) {
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
seqüência de comandos;
}
}
for (i = 0; i < N; i++) {
seqüência de comandos
}
}
else {
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
for (k = 0; k < N; k++) {
seqüência de comandos;
}
}
}
}
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 18

17) Nos trechos de programa a seguir, encontre o número de vezes que o

comando c1 é executado:
a)
(1) for (i=1; i<=N-1; i++)
(2) for (j=i+1; j<N; j++)
(3) c1;

b)
(1) for (i=N; i>0; i--)
(2) for (j=N-1; j>1; j--)
(3) c1;

c)
(1) for (i=2; i<=N-3; i++)
(2) for (j=N; j>i; j--)
(3) c1;

18) O tempo de execução de um algoritmo recursivo A é descrito pela relação de

recorrência T(n) = 7T(n/2)+n2. Um outro algoritmo recursivo B para resolver o
mesmo problema tem um tempo de execução dado pela relação T’(n) =
αT’(n/4)+n2. Usando o Teorema Master, determine qual o maior valor inteiro de α
tal que o algoritmo B seja assintoticamente mais rápido do que o algoritmo A.

19) Resolva a seguinte relação de recorrência pelo método da iteração e pelo

método Master:

T(n) = 27, para n = 1

T(n) = 2T(n/4) + n, para n > 1

20) Seja o seguinte programa em Pascal para resolver o problema clássico de

recursividade para as Torres de Hanoi:
Program Hanoi;
var discos: byte;
procedure Move (num: byte; origem, destino, temp: char);
begin
if num > 0 then begin
Move (num-1, origem, temp, destino);
writeln (origem, ’->’, destino);
Move (num-1, temp, destino, origem)
end;
begin
write (’Numero de discos: ’);
readln (discos);
Move (discos, ’A’, ’C’, ’B’)
end.

a) Defina uma relação de recorrência relacionada ao número de chamadas

recursivas, para o procedimento Move.
b) Calcule a ordem de complexidade O do programa Hanoi.
c) Na prática, o que significa o resultado obtido em b?
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 19

21) João V. Lozz diz ter desenvolvido um algoritmo de pesquisa recursivo cuja
relação de recorrência é dada por:

T(n) = 3 T(n/3) + n
T(1) = 1

Encontre a ordem de complexidade desse algoritmo.

22) Encontre a ordem de complexidade da seguinte função recursiva que

encontra o n-ésimo número da seqüência de Fibonacci:

int fib (n: int);

{
if (n==0) or (n==1) return 1
else fib = fib(n-1)+fib(n-2)
}

23) Um certo algoritmo A tem uma estrutura recursiva que permite descrever
seu tempo de computação por:
T(n) = T(⎣n/3⎦) + T(⎣n/5⎦) + n
T(1) = 1,
onde n representa o tamanho da entrada. Qual a ordem de complexidade de
pior caso desse algoritmo?
24) Encontre a ordem de complexidade do programa XPTO, no melhor caso e
no pior caso.
(1) PROGRAM XPTO;
(2) PROCEDURE P(N: INT);
(3) {
(4) IF (N > 1) THEN {
(5) //DIVIDE N EM DUAS INSTÂNCIAS N1 E N2, DE IGUAL TAMANHO, COM CUSTO N2
(6) P(N1);
(7) P(N2)
(8) }
(9) };
(10) FUNCTION F(N: INT): INT;
(11) {
(12) IF (N = 0) THEN F := 1
(13) ELSE F := 3 * F(N-2)
(14) };
(15) {
(16) read(x,y); //x e y são inteiros positivos, x é par e y>=2
(17) IF (X < Y) THEN P(X)
(18) ELSE Z := F(Y);
(19) }

25) Defina uma relação de recorrência e, a partir dela, encontre a ordem de

complexidade de cada um dos algoritmos abaixo:
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 20

a) Procedure Divide (n: int);

{
if n > 1 then {
<divide n por três, com custo n2>;
Divide(n1);
Divide(n2);
Divide(n3)
}
}

b) Procedure Doodle (n, m: int);

{ b1) suponha custos iguais para
if n > 0 then {
DrawLine(n, n, m, m); desenhar linhas de tamanhos diferentes.
DrawLine(n, m, n, m); b2) suponha custo proporcional ao
Doodle(n-1,m) tamanho das linhas desenhadas.
}

26) Apresentamos a seguir, um algoritmo recursivo para encontrar o maior e menor

elemento em um conjunto de elementos não repetidos. Encontre a complexidade
desse algoritmo.

Método MaxMin (i, j, fmax, fmin);

{
case
i = j: fmax = fmin = A[i];
i = j-1: if A[i] < A[j] { fmax = A[j];
fmin = A[i] }
else meio = ⎣(i+j)/2⎦ ;
MaxMin (i, meio, gmax, gmin);
MaxMin (meio+1, j, hmax, hmin);
fmax = max(gmax, hmax);
fmin = min(gmin, hmin)
}

Bibliografia
ƒ Algoritmos: Teoria e Prática, T. H. Cormen, C. E. Leiserson, R. L. Rivest & C.
Stein, Editora Campus, 1991
ƒ Computer Algorithms, E. Horowitz, S. Sahni & S. Rajasekaran, Computer
Science Press, 1998.
ƒ Data Structures and Algorithms, Aho, A., Hopcroft, J. F. & Ullman, J. D.
ƒ Fundamentals of Computer Algorithms, Horowitz, E. & Sahni, S.
ƒ Projeto de Algoritmos: fundamentos, análise e exemplos da Internet, Michael
Goodrich, Bookman, 2004.
ƒ Projeto e Análise de Algoritmos, Elton Silva, 2006 (anotações do professor)
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 21

Anexo A - Fundamentos Matemáticos

Somatório
n n

∑ ai = a k + a k +1 + a k + 2 + ... + a n
i=k
∑1 = n
i =1

(n − k + 1) termos
n n

∑ cai = c∑ ai
i=k i=k
n n n Atenção:
∑ ai ± bi = ∑ ai ± ∑ bi n n n
i=k i =k i =k
∑ ai * bi ≠ ∑ ai * ∑ bi
i =k i =k i=k
n n n

∑a
i =k
i / bi ≠ ∑ ai / ∑ bi
i =k i =k
Soma Aritmética (P.A) n
n(n + 1)(2n + 1)
n
(a + a n )n Soma de Quadrados ∑i 2
=
∑
i =1
a i = a1 + a 2 + ... + a n = 1
2
i =0 6

n 2 (n + 1) 2
n
Soma de Cubos ∑ i =
3

i =0 4
Soma Geométrica (P.G)
n
x n +1 − 1
∑
i =0
x =x .i

x −1
0
,x ≠1

Exponencial e Logaritmos
x0 = 1 log b 1 = 0 Convenções:

x −a = 1 / x a a = b logb a lg a = log 2 a
x a +b
= x .x
a b log c (a.b) = log c a + log c b ln a = log e a e = 2,71...
x a −b = x a / x b log c (a / b) = log c a − log c b log a = log10 a
x a .b
= (x ) = (x )
a b b a log b a = n. log b a
n
log a + b = (log a) + b
a =n
log b n log b a
log k n = (log n) k
log b a = (log c a ) /(log c b) log log n = log(log n)
log b a = 1 /(log a b)

Piso e Teto
x∈ ℜ x-1 < ⎣x⎦ ≤ x ≤ ⎡x⎤ < x+1

⎣x⎦ : piso de x, maior inteiro menor ou igual a x, ex.: ⎣2,5⎦ = 2 Para x ∈ Ζ,

⎣x/2⎦ + ⎡x/2⎤ = x
⎡x⎤ : teto de x, menor inteiro maior ou igual a x, ex.: ⎡2,5⎤ = 3 ⎡x/2⎤ - 1 < x ≤ ⎡x/2⎤
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 22

Regra de L’Hôpital
O limite da razão de duas funções é indeterminado se ambas as funções tendem
a zero, ou ambas tendem a infinito. Se f(x) e g(x) são diferenciáveis, com limites
indeterminados, então lim ( f ( x ) / g ( x )) = lim ( f ' ( x ) / g ' ( x )) .
x − >∞ x − >∞

Derivadas:

f ( x) = g ( x) ± h( x), f ' ( x) = g ' ( x) ± h' ( x)

f ( x) = g ( x).h( x), f ' ( x) = g ' ( x).h( x) + g ( x).h' ( x)
f ( x) = g ( x) / h( x), f ' ( x) = ( g ' ( x).h( x) − g ( x).h' ( x)) / h( x) 2
f ( x) = g ( x) n , f ' ( x) = n.g ( x) n −1 .g ' ( x)
f ( x) = e x , f ' ( x) = e x
f ( x) = log a x, f ' ( x) = 1 /( x. ln a )
y = f ( g ( x)), y ' = f ' ( g ( x)).g ' ( x) (regra da cadeia )

Resolvendo Relações de Recorrência

Crescimento assintótico de funções Método Master: T(n)=aT(n/b)+f(n), a≥1, b>1

f ( n) 1. Se f(n)=O(n(logba) - ε) para uma constante ε>0,

(i) Se 0 ≤ lim < ∞ , f(n) = O(g(n)).
n − >∞ g ( n) então T(n)= Θ(nlogba)

Obs.: se lim f(n)/g(n)=0, f(n) = o(g(n)) 2. Se f(n)= Θ(nlogba), então T(n)= Θ([Link] n)

f ( n)
(ii) Se 0 < lim ≤ ∞ , f(n) = Ω(g(n)) 3. Se f(n)= Ω(n(logba) + ε) para uma constante ε>0,
n − >∞ g ( n) e se af(n/b) ≤cf(n), para alguma constante c<1 e
n suficientemente grande então T(n)= Θ(f(n))
Obs.: se lim f(n)/g(n)=∞, f(n) = ω(g(n))
Relações-padrão
f ( n)
(iii) Se 0 < lim < ∞ , f(n) = Θ(g(n)) • T(n)=T(n/c) + k, k,c const, c>1, T(n)=O(logcn)
n − > ∞ g ( n) • T(n)=cT(n/c) + k, k,c const, c>1, T(n)=O(n)
• T(n)=aT(n/c) + k, k, a, c const, a>c, c>1, T(n)=O(nlogca)
• T(n)=aT(n/c) + kn, k, a, c const, c>1,
a<c, T(n)=O(n)
a=c, T(n)=O(nlgn)
a>c, T(n)=O(nlogca)

Resolvendo Relações de Recorrência

Horowitz T(n) = aT(n/b) + f(n)

T(n)= n log b a [T(1) + u(n)], a≥1, b>1 h(n) (teste) u(n) (complexidade)

k (i) O (nr), r<0 O (1)

u (n) = ∑ h(b ) j
(ii) Θ ((log n)i), i≥0 Θ ((log n)i+1/(i+1))
j =1
(iii) Ω (nr), r>0 Ω (h(n))
h(n) = f(n)/ n log b a
 ®
Análise Assintótica da Complexidade de Algoritmos Elton Silva 2007-2 23

Resolvendo Relações de Recorrência

Gersting Ross & Wright

T(n) = cT(n-1) + g(n), c constante T(n) = aT(n-1) + bT(n-2), a e b constantes ≠s de zero

(recorrências lineares de primeira ordem) (recorrências lineares de segunda ordem)
n
T (n) = c n −1T (1) + ∑ c n −i g (i ) Equação Característica (EC): x2 – ax – b = 0
n n
i =2 (a) se a EC tem raízes r1 e r2, então T(n) = c1 r1 + c 2 r2
(b) se a EC tem raiz única r, então T(n) = c1 r n + c 2 nr n

Combinatória Básica
n! n! n
P(n, r) =
(n − r )!
0 ≤r ≤ n C(n, r) =
r!(n − r )!
0≤r≤n (a+b)n = ∑ C ( n, k ) a
k =0
n−k
bk

P(n, r) = nr
C(n+r-1, r) =
(n + r − 1)!
r!( n − 1)!