Comparação assintótica de funções

We want a statement about software,
not hardware.

Ao ver uma expressão como n+10 ou n²+1, a maioria das pessoas pensa automaticamente em valores pequenos de n. 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

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

têm todas a mesma taxa de crescimento e portanto são todas equivalentes. (A expressão têm a mesma taxa de crescimento não significa que têm a mesma derivada!)

A matemática que se interessa apenas pelos valores enormes de n é chamada assintótica (= asymptotic). Nessa matemática, as funções são classificadas em ordens assintóticas. Antes de definir essas ordens, entretanto, vamos examinar alguns exemplos.

Exemplos preliminares

Suponha que f e g são duas funções definidas no conjunto dos números naturais. Para comparar o comportamento assintótico de f e g, é preciso resolver o seguinte problema: encontrar um número c tal que f(n) ≤ c g(n) para todo n suficientemente grande. Mais explicitamente: encontrar números c e N tais que f(n) ≤ c g(n) para todo n maior que N. É claro que os números c e N devem ser constantes, ou seja, não devem depender de n. Veja alguns exemplos concretos:

Exemplo A. Encontre números c e N tais que 3n²/2 + 7n/2 + 4 ≤ c n² para todo n maior que N. Eis uma solução: c = 6 e N = 3. Esse par de números tem a propriedade desejada pois

3`n`²/2 + 7`n`/2 + 4	≤	2`n`² + 4`n` + 4
	≤	2`n`² + `nn` + `nn`
	=	6 `n`²

sempre que n > 3.

Exemplo B. Encontre números c e N tais que 2n² + 30n + 400 ≤ c n² para todo n maior que N. Como mostraremos a seguir, os números c = 432 e N = 0 constituem uma solução. De fato, para todo n > 0 tem-se

2`n`² + 30`n` + 400	≤	2`n`² + 30`n`² + 400`n`²
	=	432 `n`² .

Os números c = 4 e N = 29 constituem uma solução igualmente boa. Eis a prova: Se n > 29 então

2`n`² + 30`n` + 400	≤	2`n`² + `nn` + `nn`
	=	4 `n`² .

Exemplo C. Queremos encontrar números c e N tais que 300 + 20/n ≤ c n⁰ para todo n maior que N. Eis uma solução do problema: c = 301 e N = 19. De fato, 300 + 20/n ≤ 300 + 1 = 301 para todo n ≥ 20.

Exemplo D. Existem números c e N tais que 20n² + 2n + 100 ≤ c (n³ − 10) para todo n maior que N? A resposta é afirmativa; basta tomar c = 2 e N = 21. De fato,

20`n`² + 2`n` + 100	<	20`n`² + `nn` + `n`²
	=	22 `n`²
	≤	`nn`²
	=	`n`³
	<	`n`³ + `n`³ − 20
	=	2 (`n`³ − 10)

para todo n ≥ 22.

Exemplo E. Existem números c e N tais que n³ ≤ c n² para todo n maior que N? A resposta é negativa. Para provar isso, suponha por um momento que c e N têm a propriedade. Então

n ≤ c

para todo n > N. Mas isso é impossível, o que mostra que c e N não existem, CQD.

Exemplo F. Queremos encontrar números c e N tais que n² − 100n ≤ c 200n para todo n maior que N. Esse problema não tem solução, como mostraremos a seguir. Suponha por um momento que existe uma solução (c, N). Então n² − 100n ≤ c 200n para todo n > N. Logo, n − 100 ≤ 200c e portanto

n ≤ 200 c + 100

para todo n > N. Mas isso é absurdo. Esse absurdo mostra que o problema não tem solução, CQD.

Exemplo G. Seja a um número maior que 1. Queremos encontrar números c e N tais que log_a n ≤ c lg n para todo n maior que N. Uma das soluções do problema consiste em c = 1 / lg a e N = 1 pois

log_a `n` =	1	lg `n`
	lg `a`

para todo n > 1. (Veja o Apêndice.)

Exemplo H. Encontrar números c e N tais que ⌈n/2⌉ + 10 ≤ c n para todo n maior que N. Uma solução do problema tem c = 1 e N = 21. De fato,

⌈`n`/2⌉ + 10	≤	`n`/2 + 1 + 10
	=	`n`/2 + 11
	≤	`n`/2 + `n`/2
	=	`n`

para todo n ≥ 22. Outra solução consiste em c = 10 e N = 1, uma vez que ⌈n/2⌉ + 10 ≤ n/2 + 1 + 10 = n/2 + 11 ≤ 10n para todo n > 1.

Exercícios 1

What I hear, I forget.
What I see, I remember.
What I do, I understand.

— Confucius

Qual a diferença entre assintótico e assintomático?
O que há de errado com o seguinte raciocínio? Existem números c e N tais que n³ ≤ c n² para todo n maior que N. De fato, basta tomar c = n e N = 1. (Compare com o exemplo E.)
★ Queremos provar que 3n² + 7n ≤ cn² para todo n suficientemente grande. Critique a seguinte prova: Se 3n² + 7n ≤ c n² então 3n + 7 ≤ c n, supondo n > 0. Logo, c ≥ 3 + 7/n. Logo, c ≥ 3 + 7 é suficiente. Logo, c ≥ 10 e n > 0. Fim da prova.
Encontre números c e N tais que 2 n lg n − 10 n + 100 lg n ≤ c n lg n para todo n maior que N.
★ Encontre números c e N tais que 2ⁿ⁺¹ ≤ c 2ⁿ para todo n maior que N. Agora encontre números c e N tais que 2ⁿ ≤ c 2^n/2 para todo n maior que N.
★ Encontre números c e N tais que n ≤ c 2ⁿ para todo n maior que N. (Veja o Apêndice.) Agora encontre números c e N tais que lg n ≤ cn para todo n maior que N.
É verdade que existem números c e N tais que n ≤ c 2^n/4 para todo n maior que N? (Veja exercício anterior.)
Sejam f e g as funções definidas por f(n) = n²/10 e g(n) = n. É verdade que existem números c e N tais que f(n) ≤ c g(n) para todo n maior que N?

Ordem O

Para definir o conceito de ordem Ο, 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 M tal que f(n) ≥ 0 para todo n maior que M.

Agora podemos definir a ordem Ο. (Esta letra é um Ó maiúsculo. Ou melhor, um ômicron grego maiúsculo, de acordo com Knuth.)

Definição: Dadas funções assintoticamente não-negativas f e g, dizemos que f está na ordem Ó de g e escrevemos f = Ο(g) se existem constantes positivas c e N tais que f(n) ≤ c g(n) para todo n maior que N.

(No lugar de dizer f está na ordem Ó de g, há quem diga f é da ordem de no máximo g.)

A expressão f = Ο(g) é útil e poderosa porque esconde informações irrelevantes: a expressão informa o leitor sobre a relação entre f e g sem desviar sua atenção para os valores de c e N.

(A notação f = Ο(g) é conhecida como notação assintótica, ou notação de Landau. O sinal = nessa notação é um abuso pois não representa igualdade no sentido usual. Quem sabe seria melhor escrever f está em Ο(g) ou f é Ο(g).)

Exemplo I. Suponha que f(n) = 2n² + 30n + 400 e g(n) = n². É óbvio que f e g são assintoticamente não-negativas. Além disso, como mostramos no exemplo B acima, f(n) ≤ 4 g(n) para todo n > 29. Portanto, f = Ο(g).

Exemplo J. É claro que as funções 300 + 20/n e 301n⁰ são assintoticamente não-negativas. Além disso, como mostramos no exemplo C acima, 300 + 20/n ≤ 301n⁰ para todo n > 19. Portanto, 300 + 20/n = Ο(n⁰). (Poderíamos escrever Ο(1) no lugar de Ο(n⁰), mas essa última expressão ajuda a lembrar que a variável é n.)

Exemplo K. Considere as funções 20n² + 2n + 100 e n³ − 10. Observe que ambas são assintoticamente não-negativas pois são positivas quando n ≥ 3. Além disso, 20n² + 2n + 100 ≤ 2 (n³ − 10) para todo n > 21, como mostramos no exemplo D acima. Portanto, 20n² + 2n + 100 está em Ο(n³ − 10).

Exemplo L. A função n³ não está em Ο(n²) pois, como mostramos no exemplo E acima, não existem números c e N tais que n³ ≤ c n² para todo n maior que N.

Exemplo M. Não é verdade que n² − 100n = Ο(200n) porque não existem números c e N tais que n² − 100n ≤ c 200n para todo n maior que N, como mostramos no exemplo F acima.

Exemplo N. Para qualquer a > 1, as funções log_a n e lg n são assintoticamente não-negativas pois ambas são positivas quando n ≥ 2. Além disso, log_a n = lg n / lg a para todo n > 1, como já observamos no exemplo G. Logo, log_a n = Ο(lg n).

Exemplo O. É óbvio que as funções ⌈n/2⌉ + 10 e n são assintoticamente não-negativas. Além disso, ⌈n/2⌉ + 10 ≤ 10n para todo n > 1, como mostramos no exemplo H. Logo, ⌈n/2⌉ + 10 = Ο(n).

Exercícios 2

Suponha que as funções f e g são assintoticamente não-negativas. Critique as seguintes tentativas de definição da classe Ο: "Dizemos que f está em Ο(g) se …
1. … f(n) ≤ c g(n) para algum n suficientemente grande e todo c positivo."
2. … para todo n suficientemente grande existe c positivo tal que f(n) ≤ c g(n)."
3. … f(n) ≤ c g(n) para todo n positivo e algum c positivo."
4. … existem números positivos c, N e n ≥ N tais que f(n) ≤ c g(n)."
5. … existe um número positivo N tal que f(n) ≤ c g(n) para algum número positivo c e para todo n ≥ N."
Faz sentido lógico dizer f(n) está em Ο(n²) para n ≥ 10?
★ Fica bem dizer f(n) = Ο(n²) com c = 10 e N = 100? Como reformular isso?
★ Mostre que a cláusula n suficientemente grande na definição da classe Ο é supérflua quando estamos lidando com funções estritamente positivas.
Critique o seguinte raciocínio: A derivada de 4n² + 2n é 8n + 2. A derivada de n² é 2n. Como 8n+2 > 2n, podemos concluir que 4n²+2n cresce mais que n² e portanto 4n²+2n não é Ο(n²). Agora critique o seguinte raciocínio: A derivada de 4n² + 2n é 8n + 2. A derivada de 9n² é 18n. Como 8n+2 ≤ 18n para n ≥ 1, podemos concluir que 4n²+2n é Ο(9n²).
É verdade que 100n = Ο(n)? É verdade que n²/100 = Ο(n)?
É verdade que 10n² + 200n + 500/n = Ο(n²)?
É verdade que n² − 200n − 300 = Ο(n)?
★ Coeficientes binomiais. Seja C(n, k) o número de combinações de n objetos tomados k a k. Mostre que C(n, 2) = Ο(n²). Mostre que C(n, 3) = Ο(n³). É verdade que, para qualquer número natural k tem-se C(n, k) = Ο(n^k)? [Solução]
★ É verdade que 2ⁿ⁺¹ está em Ο(2ⁿ)? É verdade que 2ⁿ está em Ο(2^n/2)?
★ É verdade que 3ⁿ está em Ο(2ⁿ)? É verdade que 2ⁿ está em Ο(3ⁿ)?
★ É verdade que lg n = Ο(log₃ n)? É verdade que log₃ n = Ο(lg n)?
★ É verdade que ⌈lg n⌉ = Ο(lg n)?
Prove que n lg n + 10n^3/2 está em Ο(n lg n).
Mostre que lg (100n³ + 200n + 300)² = Ο(lg n).
É verdade que 2n¹⁰²⁴ = Ο(2ⁿ)?
É verdade que n^2/3 está em Ο(√n)? É verdade que √n está em Ο(n^2/3)?
Qual o maior número natural k tal que n^1/k = Ο(lg n)?
Transitividade. Suponha que f = Ο(g) e g = Ο(h). Prove que f = Ο(h).
Coloque as seguinte funções em ordem crescente de Ο( ): n, √n, log n, 2ⁿ, n / (log n), 2^√n, log log n, log² n, ∛n.

Ordem Ômega

A expressão f = Ο(g) tem sabor de f ≤ g. Agora precisamos de um conceito que tenha o sabor de f ≥ g.

Definição: Dadas funções assintoticamente não-negativas f e g, dizemos que f está na ordem Ômega de g e escrevemos f = Ω(g) se existe um número positivo c tal que f(n) ≥ c g(n) para todo n suficientemente grande.

(No lugar de f está na ordem Ômega de g, há quem diga f é da ordem de pelo menos g.)

(O sinal = na notação de Landau f = Ω(g) é um abuso pois não representa igualdade no sentido usual. Provavelmente é melhor dizer f está em Ω(g) ou f é Ω(g).)

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

Exemplo P. É fato que n/2 − 100 = Ω(n). Confira a prova: Para todo n ≥ 400, tem-se

n/2 − 100 ≥ n/2 − n/4 = (1/4) n.

Além disso, é evidente que as duas funções são assintoticamente não-negativas.

Exemplo Q. A função n²/2 − 100 n − 300 está em Ω(n). De fato, para todo n ≥ 400, tem-se

`n`²/2 − 100 `n` − 300	≥	`n`²/2 − (`n`/4) `n` − `n`²/8
	=	(1/2 − 1/4 − 1/8) `n`²
	=	(1/8) `n`²
	≥	(400/8) `n`
	≥	50 `n`.

Além disso, n²/2 − 100 n − 300 ≥ 50 n > 0 para todo n ≥ 400 e portanto as duas funções em discussão são assintoticamente não-negativas.

Exercícios 3

Sejam f e g duas funções assintoticamente não negativas. Prove que f = Ο(g) se e somente se g = Ω(f).
Coeficientes binomiais. Seja C(n, k) o número de combinações de n objetos tomados k a k. Mostre que C(n, 2) = Ω(n²). Mostre que C(n, 3) = Ω(n³). É verdade que, para qualquer número natural k tem-se C(n, k) = Ω(n^k)? [Solução]
Prove que 2n² − 20n − 50 = Ω(2n).
Prove que 2n² − 20n − 50 = Ω(n^3/2).
Prove que n² − n − 10 = Ω(n lg n).
É verdade que 100n² + 10000 = Ω(n² lg n)?
Prove que 100 lg n − 10n + 2 n lg n está em Ω(n lg n).
É verdade que 2ⁿ⁻² está em Ω(2ⁿ)? É verdade que 3^n/2 está em Ω(2ⁿ)?

Ordem Theta

Além dos conceitos que têm os sabores de f ≤ g e de f ≥ g, precisamos de um que tenha o sabor de f = g.

Definição: Dizemos que duas funções assintoticamente não negativas f e g são da mesma ordem e escrevemos f = Θ(g) se f = Ο(g) e f = Ω(g). Trocando em miúdos, f = Θ(g) significa que existe constantes positivas c e d tais que c g(n) ≤ f(n) ≤ d g(n) para todo n suficientemente grande.

(No lugar de dizer f está na ordem Θ de g, há quem diga, simplesmente, que f é da ordem de g.) Seguem alguns exemplos.

Exemplo R. As funções n², (3/2) n², 9999 n², n²/1000 e n²+100n pertencem todas à ordem Θ(n²).

Exemplo S. Para quaisquer números a e b maiores que 1, a função log_a n está em Θ(log_b n).

Exercícios 4

Mostre que f = Θ(g) se e somente se g = Θ(f).
Quais das afirmações abaixo estão corretas?
- (3/2) n² + (7/2) n − 4 = Θ(n²)
- 9999 n² = Θ(n²)
- n²/1000 − 999 n = Θ(n²)
- lg n + 1 = Θ(log₁₀ n)
- ⌊lg n⌋ = Θ(lg n)

Onde as funções estão definidas?

A discussão acima supõe, implicitamente, que todas as funções estão definidas no conjunto dos números naturais. Mas tudo continua funcionando se as funções estiverem definidas em algum outro domínio. Veja alguns exemplos de domínios:

números naturais maiores que 99,
potências inteiras de 2 (ou seja, 2⁰, 2¹, 2², etc.),
potências inteiras de 1½,
números racionais maiores que ½.

A notação Ο pode ser usada em qualquer desses domínios. Por exemplo, se f é uma função assintoticamente não-negativa definida nas potências inteiras de 2, dizer que f(n) = Ο(n²) é o mesmo que dizer que existe um número positivo c tal que f(2^k) ≤ c 2^2k para todo natural k suficientemente grande.

As mesmas observações se aplicam à notação Ω e à notação Θ.

Análise de algoritmos

A análise de algoritmos procura estimar o consumo de tempo de um algoritmo em função do tamanho, digamos n, de sua entrada.

Suponha que f(n) é o consumo de tempo de um algoritmo A para um certo problema e g(n) é o consumo de tempo de um algoritmo B para o mesmo problema. Para comparar as eficiências de A e B, a análise de algoritmos estuda o comportamento de f e g para valores grandes de n. Se f = Ο(g), o algoritmo A é considerado pelo menos tão eficiente quanto B. Se, além disso, f não está em Θ(g), o algoritmo A é considerado mais eficiente que B.

As funções mais comuns na análise de algoritmos são lg n, n, n lg n, n² e n³. A seguinte tabela mostra os valores dessas funções para n entre 10³ e 10⁷. Para simplificar, a tabela mostra o logaritmo na base 10. Cada função da tabela é dominada pela seguinte e esse efeito cresce com o valor de n.

log `n`	3	4	5	6	7
`n`	1000	10000	100000	1000000	10000000
`n` log `n`	3000	40000	500000	6000000	70000000
`n`²	1000000	100000000	10000000000	1000000000000	100000000000000
`n`³	1000000000	1000000000000	1000000000000000	1000000000000000000	1000000000000000000000