EXERCÍCIOS SOBRE COMPLEXIDADE DE ALGORITMOS (notações
Prolo, Algoritmos e Estruturas de Dados III, T 128, ago/2004
1. Mostre que 2. Mostre que e )
.
.
3. Mostre que para todo , 4. Mostre que para todo , 5. Mostre que para todo e constantes , tal que #"%$ ,
!
'& () ()& & & 6. Mostre que para todo e constantes , tal que #"%$ ,
!
& () () & & & **
0
0
ou mostre que +, &.- .
Mostre que +, &.- /
0
0
- $,$ &.3 $ ou mostre que - &21 $ - $,$ &.3 $ .
Mostre que - &21 $
Mostre que as duas definições da notação são equivalentes. Sejam 4576089;:< :
0
Def 1: 4
sse >@?ABC
tal que DE!F4 HG2?6 I & B
=
6
0
$
Def 2: 4
6= sse >@?AJ
KC $ tal que D " !L*4 IHG2?J6 I .
Neste exercício e no próximo você vai comparar as funções 4 1 M -9N (exponencial base 2) com
4 - IOP para alguma constante QR (na verdade 4 - é uma família de funções chamadas
polinomiais, e.g., 1 JSJ J T ). Embora seja intuitivamente óbvio que f1 cresce muito mais
- N , devido a natureza bastante
rapidamente do que f2, não é fácil provar formalmente que UV
7.
8.
9.
10.
diversa destas duas funções. Parta do seguinte fato, do cálculo infinitesimal,
WYX[Z
NA\L] - N $ 0
- N .
para qualquer constante ! , e tente provar que ^V
11. Mostre que para todo _! , - N (veja informações do exercício anterior).
12. Usando resultados anteriores desta lista mostre que para qualquer polinômio ` de grau ab
` Icd .
13. Usando resultados anteriores desta lista e transitividade de e mostre que para quaisquer dois
polinômios ` 1 e ` - de mesmo grau 0!%` 1 ';e ` - I7 e ` 1 I
fg ` - Ih
14. Usando resultados anteriores desta lista mostre que para qualquer polinômio ` de grau ab
- N .
` I d