PAA

Expresse a func~ao n3=1000 ???? 100n2 ???? 100n + 3 em termos da notac~ao :
2. Analise o algoritmo abaixo e identique seu pior caso usando a notac~ao 
exibe matriz 3D(M)
for i 1 to comprimento x[M]
for j 1 to comprimento y[M]
for k 1 to comprimento z[M]
do escreva(M[i][j][k]))
3. Considere a ordenac~ao de n numeros armazenados no arranjo A, localizando primeiro
o menor elemento de A e trocando esse elemento com o contido em A[1]. Em seguida,
encontre o segundo menor e troque com o da posic~ao A[2]. Continue dessa maneira
para os n - 1 primeiros elementos de A. Escreva o pseudocodigo para esse algoritmo
conhecido como ordenac~ao por selec~ao e calcule o tempo do pior caso de execuc~ao
deste algoritmo escrevendo-o segundo a notac~ao .
4. Suponhamos 2 algoritmos de ordenac~ao, A e B. Vamos executa-los na mesma maquina.
A e executado em 8n2 etapas, enquanto B necessita de 64n log n. Qual dos dois e melhor?
Em que condic~oes? (Suponha n pot^encia de 2).
5. Coloque em ordem crescente de complexidade as principais classes de problemas
listadas a seguir.
O(n!); O(n log n); O(n); O(log n); O(1); O(2n); O(n3);O(n2)
6. Dizemos que f(n) e O(g(n)) se f(n) < c  g(n) para todo n > n0. Sabemos que um
algoritmos com custo (n+1)2 e O(n2). Encontre valores para c e n0 que conrmem essa
armac~ao.
7. Dado um algoritmo para encontrar o maior valor em um vetor:
int max(int vet[ ], int n)f
int maior = vet[0];
for (int i = 1; i < n; i++) f
if (vet[i] > maior) f
maior = vet[i];
g
g
return maior;
g
Qual a complexidade de pior caso O desse algoritmo? Esse algoritmo e otimo? Justi-
que.
2