Complexidade_Atividade1_resolucao

Prévia do material em texto

Atividade A1 
Análise de Algoritmos Iterativos e Notação Assintótica 
Data limite de entrega: 14 de outubro 
 
1) Considerando o algoritmo abaixo e as operações primitivas estudadas em 
sala (atribuição, chamada de função, acesso ao elemento de um arranjo, 
operações aritméticas, retorno de função e comparação entre dois 
elementos). 
 
módulo Enigma ( inteiro A[], inteiro n ) 
início 
inteiro a, i; 
a = 0; 
para (i = n - 1; i >= 0; i--) faça 
 se ((A[i] % 4 = 0) e (A[i] % 5 = 0)) então 
 a = a + A[i]; 
 fim-se 
fim-para 
retorna a; 
fim. 
 
Pede-se: 
a) O que faz o algoritmo enigma? 
Resposta: 
O algoritmo realiza a soma de todos os valores do conjunto A que são 
múltiplos de 4 e 5 ao mesmo tempo. 
 
b) Qual a configuração de A para o pior e melhor caso? 
Resposta: 
O melhor caso ocorre quando o comando condicional é falso, ou seja, quando 
não há elemento no conjunto A que seja múltiplo de 4 e/ou 5. 
O pior caso ocorre quando o comando condicional é verdadeiro (pois, executa o 
comando a = a + A[i]), ou seja, quando todos elementos no conjunto A são 
múltiplo de 4 e 5 ao mesmo tempo. 
 
c) Qual a T(n), em termos de operações primitivas, no melhor caso? 
Resposta: 
a = 0; 
para (i = n - 1; i >= 0; i--) faça 
 se ((A[i] % 4 = 0) e (A[i] % 5 = 0)) 
então 
 a = a + A[i]; 
 fim-se 
fim-para 
retorna a; 
----- 1 
----- 2 + ∑ 𝟏𝒏−𝟏𝒊= −𝟏 + ∑ 𝟖
𝒏−𝟏
𝒊= 𝟎 
 
 
 
----- 1 
---------------------------------- 
T(n) = 4 + n + 1 + 8n = 9n + 5 
d) Qual a T(n), em termos de operações primitivas, no pior caso? 
Resposta: 
a = 0; 
para (i = n - 1; i >= 0; i--) faça 
 se ((A[i] % 4 = 0) e (A[i] % 5 = 0)) 
então 
 a = a + A[i]; 
 fim-se 
fim-para 
retorna a; 
----- 1 
----- 2 + ∑ 𝟏𝒏−𝟏𝒊= −𝟏 + ∑ 𝟏𝟏
𝒏−𝟏
𝒊= 𝟎 
 
 
 
----- 1 
---------------------------------- 
T(n) = 4 + n + 1 + 11n = 12n 
+ 5 
 
e) Qual o  (Theta), no pior caso, por que (Prove pela definição de Tetha)? 
Resposta: 
Pela definição de Theta temos: Dada duas funções positivas f(n) e g(n), f(n) é 
(g(n)) se existem números positivos c1, c2 e n0 tais que c1g(n)  f(n)  c2g(n) 
para todo n  n0. 
Logo, f(n) = 12n + 5 
 
c1g(n)  12n + 5  c2g(n) para todo n  n0. Fazendo g(n) = n. 
c1n  12n + 5  c2n para todo n  n0. Fazendo c1 = 12 e c2= 13. 
12n  12n + 5  13n para todo n  1, ou seja, n0 = 5. 
Portanto, f(n) é (n). 
 
 
2) Dado o seguinte trecho de código, qual a expressão de k, em função de n ? 
 k=0; 
 for (i=2; i <= n; i++) 
 for (j=n; j >= i; j--) 
 k=k+1; 
 
Resposta: 
k = ∑ ∑ 𝟏𝒏𝒋=𝒊
𝒏
𝒊=𝟐 = ∑ (𝒏 − 𝒊 + 𝟏)
𝒏
𝒊=𝟐 = ∑ 𝒏
𝒏−𝟏
𝒊=𝟏 − ∑ (𝒊
𝒏−𝟏
𝒊=𝟏 + 𝟏) +
 ∑ 𝟏𝒏−𝟏𝒊=𝟏 
 
k = 𝒏𝟐 − 𝒏 − 
𝟏
𝟐
(𝒏 − 𝟏)𝒏 + 𝟐 (𝒏 − 𝟏) = 
𝟏
𝟐
𝒏𝟐 +
𝟏
𝟐
𝒏 - 2= 
 
n(n + 1) /2 - 2 
 
3) Considerando o módulo Enigma abaixo que: 
 
módulo Enigma ( inteiro A[], inteiro n ) 
início 
 inteiro a, i; 
 a ← 0; 
 para (i ← n - 1; i >= 0; i--) faça 
 se (A[i] % 2 == 0) então 
 a ← a + A[i]; 
 fim-se 
 fim-para 
retorna a; 
fim. 
 
Pede-se: 
a) Qual a funcionalidade do módulo Enigma (o que ele faz)? 
Resposta: 
O módulo "realiza a soma de todos os valores do conjunto A que são 
pares" 
 
b) Qual a configuração de A para o pior e melhor caso? 
Resposta: 
O melhor caso ocorre quando o comando condicional é falso, ou seja, quando 
não há elemento par no conjunto A. 
O pior caso ocorre quando o comando condicional é verdadeiro (pois, executa o 
comando a = a + A[i]), ou seja, quando todos elementos no conjunto A são pares. 
 
c) Qual a T(n), em termos de operações primitivas, no pior caso? 
Resposta: 
a ← 0; 
para (i ← n - 1; i >= 0; i--) faça 
 se ((A[i] % 2 == 0)) então 
 a ← a + A[i]; 
 fim-se 
fim-para 
retorna a; 
----- 1 
----- 2 + ∑ 𝟏𝒏−𝟏𝒊= −𝟏 + ∑ 𝟕
𝒏−𝟏
𝒊= 𝟎 
 
 
 
----- 1 
---------------------------------- 
T(n) = 4 + n + 1 + 7n = 8n + 5 
 
 
4) Um determinado algoritmo foi analisado, tendo por base as seis 
operações primitivas estudadas em aula, e foi obtido o T(n) na forma de 
um somatório abaixo. Pede-se: faça o seu cálculo e obtenha a função 
T(n) resultante. 
 
T(n) = ∑ ∑ 𝟏𝒏𝒋=𝒊
𝒏
𝒊=𝟏 
Resposta: 
T(n) = ∑ ∑ 𝟏𝒏𝒋=𝒊
𝒏
𝒊=𝟏 = ∑ (𝒏 − 𝒊 + 𝟏)
𝒏
𝒊=𝟏 = ∑ 𝒏
𝒏
𝒊=𝟏 − ∑ 𝒊
𝒏
𝒊=𝟏 +
 ∑ 𝟏𝒏𝒊=𝟏 
T(n) = 𝒏𝟐 − 
𝟏
𝟐
𝒏(𝒏 + 𝟏) + 𝒏 = 
𝟏
𝟐
𝒏𝟐 +
𝟏
𝟐
𝒏 = n(n + 1) /2 
 
5) O trecho de algoritmo para calcular a nn que utiliza uma repetição para 
a contagem das multiplicações é dado por: 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Considerando todas as operações primitivas estudadas em sala, pede-se: 
a) Calcule a equação de complexidade T(n) para n_elevado_n( inteiro n ). 
Resposta: 
função inteiro n_elevado_n ( inteiro n) 
início 
 inteiro res, i; 
 res ← 1; -------------------------------------------- 1 + 
 para (i ← 1; i ≤ n; i++) faça -------------------------------- 1 + (n+1) + n + 
 res ← res * n; -------------------------------------- 2n + 
 retorna res; ----------------------------------------------- 1 
fim. 
------------------------------------------------------------------------------------------------ 
T(n) = 4n + 4 operações. 
b) Calcule a equação de complexidade T(n) para n_elevado_n2( inteiro n ). 
Resposta: 
função inteiro n_elevado_n2( inteiro n) 
início 
 inteiro res, i; 
 res ← n ------------------------------------------- 1 + 
 para (i ← 1; i < n; i= i *2) faça ----------------- 1 + theto( log2 n ) + (theto (log2 n ) - 1) * 2 
função inteiro n_elevado_n ( inteiro n) 
início 
 inteiro res, i; 
 res ← 1; 
 para (i ← 1; i ≤ n; i++) faça 
 res ← res * n; 
 retorna res; 
fim. 
 
Se n for um múltiplo de 2, como: 1, 2, 4, 8, 16, 32,... 
O algoritmo anterior que calcula nn pode ser reescrito 
para: 
 
função inteiro n_elevado_n2( inteiro n) 
início 
 inteiro res, i; 
 res ← n 
 para (i ← 1; i < n; i= i *2) faça 
 res ← res * res; 
 retorna res; 
fim. 
 
 res ← res * res; ----------------------------- (theto (log2 n ) - 1) * 2 
 retorna res; ------------------------------------------ 1 
fim. 
------------------------------------------------------------------------------------- 
T(n) = 5 * theto (log2 n) - 1 operações. 
c) Determine o O-grande dos dois algoritmos pela definição. Necessário 
determinar c e no. 
 
Resposta: 
A definição de O-Grande diz: Dada duas funções positivas f(n) e g(n), f(n) é O(g(n)) se 
existem números positivos c e n0 tais que f(n)  cg(n) para todo n  n0. 
 
Encontrando os O-Grandes: 
Algoritmo opção a) T (n) = 4n + 4 e fazendo g(n) = n 
Assim, 
 
4n + 4  c n para todo n  n0. 
fazendo c = 5 e no = 4 
4n + 4  5 n para todo n  4, 
 
Portanto, T(n) = O(n) 
 
Algoritmo opção b) T (n) = 5 * theto (log2 n) - 1 e fazendo g(n) = log2 n 
 
Assim, 
 
5 * theto (log2 n) - 1  c log2 n para todo n  n0. 
fazendo c = 5 e no = 2 
5 * theto (log2 n) - 1  5 log2 n para todo n  2. 
 
Portanto, T(n) = O(log2 n). 
 
 
6) Considere os 5 algoritmos abaixo que determinam o enésimo termo da 
sequência de Fibonacci. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
a) Baseado nos estudos realizados em sala, apresente as complexidades 
(O-Grande) de cada um dos algoritmos.(Obs.: Não precisa calcular, 
basta apresentar o O-Grande) 
 
Resposta: 
fib_1 = O(n); 
fib_2 = O(lg n); 
fib_4 = O(n); 
 
b) Utilizando o algoritmo fib_4, determine a equação de complexidade 
(T(n)) considerando todas as operações primitivas. (Supor que a 
declaração "inteiro v[n+1]" contém 2 operações primitivas). 
Resposta: 
função inteiro fib_4( inteiro n ) 
início 
 inteiro v[n+1], i = 1; ------------------------------------- 2 + 1 + 
 v[0] = 0;------------------------------------- 2 + 
função inteiro fib_1( int n ) 
início 
 se (n < 2) retorna n; 
 senão 
 início 
 inteiro ant = 1, preant = 1, atual; 
 para (inteiro i = 3; i <= n; i++) 
 início 
 atual = ant + preant; 
 preant = ant; 
 ant = atual; 
 fim 
 retorna atual; 
 fim 
fim 
função inteiro fib_2(n) 
início 
 inteiro a, b, c, d, i = n-1; 
 se (n <= 0) retorna 0; 
 (a, b) = (1, 0); 
 (c, d) = (0, 1); 
 enquanto (i > 0) faça 
 início 
 se (i mod 2 == 0) então 
 (a, b) = (db + ca, d(b+a) + cd) 
 (c,d) = (c2 + d2, d (2c + d)) 
 i = i div 2; 
 fim 
 retorna a + b; 
fim. 
 
função inteiro fib_4( inteiro n ) 
início 
 inteiro v[n+1], i = 1; 
 v[0] = 0; 
 v[1] = 1; 
 enquanto (i < n) faça 
 início 
 v[i+1] = v[i] + v[i-1]; 
 i = i + 1; 
 fim 
 retorna v[n]; 
fim. 
 
 v[1] = 1; ------------------------------------ 2 + 
 enquanto (i < n) faça ------------------------------------- 1 (para n = 0) e n 
(para n .> 0) + 
 início 
 v[i+1] = v[i] + v[i-1]; ------------------------------------- (n-1) * 7 + 
 i = i + 1; ------------------------------------- (n-1) * 2 + 
 fim 
 retorna v[n]; ------------------------------------- 2 
fim. 
__________________________________________________________
_________________ 
n = 0 => T(n) = 10 
n > 0 => T(n) = 9 + n + 7 * (n-1) + 2 * (n-1) = 10n + 9 - 9 = 10n. 
 
7) Suponha uma matriz Anxn na qual todos os elementos de cada linha estão 
ordenados em ordem crescente e os dois algoritmos abaixo procuram a 
existência de um elemento chave dentro das linhas da matriz. Ao encontrar 
o elemento chave na linha i insere em um vetor POS a posição (coluna) na 
qual o elemento chave foi encontrado dentro da i-ésima linha de A ou -1 se 
não achar. 
 
Pede-se: 
a) Calcular os tempos T(n) em termos SOMENTE do NÚMERO MÁXIMO DE 
COMPARAÇÕES NECESSÁRIAS (pior caso) para encontrar o elemento chave 
em cada linha da matriz A para: 
módulo inteiro [] alg_I(inteiro A[][], inteiro n, 
inteiro chave) 
início 
 inteiro i, j, POS[]; logica achou; 
 para (i  0; i < n; i ++) faça 
 achou  falso; 
 para (j  0; ((j < n) e (não achou)); j ++) faça 
 se (A[i][j] == chave) então 
 POS[i]  j; achou  verdadeiro 
 fim-para 
 se (não achou) então POS[i]  -1; 
 fim-para 
 retorna POS; 
fim 
módulo inteiro [] alg_II(inteiro A[][], inteiro n, 
inteiro chave) 
início 
 inteiro i, f, l, m; lógica achou; 
 para (i  0; i < n; i ++) faça 
 f  0; l  n-1; achou  falso; 
 enquanto((f <= l) e ( não achou)) faça 
 m  (f + l) div 2; 
 se (chave == A[i][m]) então 
 POS[i]  m; achou  verdadeiro; 
 senão se (chave < A[i][m]) então 
 l  m-1; 
 senão 
 f  m + 1; 
 fim-enquanto 
 se (não achou) então POS[i]  -1; 
 fim-para 
 retorna POS; 
fim. 
b) Qual o O-grande de cada algoritmo. Mostre pela definição de O-grande 
encontrando uma constante c e n0 que os comprove. Sem a demonstração este 
item não será avaliado. 
a.1) alg_I; e b) 
 
 
 
 
 
 
 
 
 
 
 
 
 
a.2) alg_II; e b) 
 
módulo inteiro [] alg_I(inteiro A[][], inteiro n, 
inteiro chave) 
início 
 inteiro i, j, POS[]; logica achou; 
 para (i  0; i < n; i ++) faça 
 achou  falso; 
 para (j  0; ((j < n) e (não achou)); j ++) faça 
 se (A[i][j] == chave) então 
 POS[i]  j; achou  verdadeiro 
 fim-para 
 se (não achou) então POS[i]  -1; 
 fim-para 
 retorna POS; 
fim 
a) 
T(n) = n x n = n2 
 
b) 
f(n) é O(g(n)) se  c  R+ e  n0  Z+ 
tal que 
f(n)  c g(n) , n  n0 
 
Então, seja g(n) = n2 
 
n2  c n2, n  n0 
 
fazendo c = 1 e n0 = 0 
 
n2  n2, n  0 
 
portanto, T(n) = O(n2). 
 
c) Baseado no item “a” e “b”, a que conclusão pode-se chegar? 
Como a complexidade Talg_I(n) = O(n) > Talg_II(n) = O(n log2 n) pode-se chegar a 
conclusão que o Algoritmo II é mais eficiente que o Algoritmo I e seria mais 
indicado para resolver esse problema. 
8) Considerando o algoritmo e as operações primitivas estudadas em sala 
(atribuição, chamada de função, acesso ao elemento de um arranjo, 
operações aritméticas, retorno de função e comparação entre dois 
elementos). 
função inteiro produto(inteiro n, inteiro m) 
início 
 inteiro r; 
 r  0; 
 enquanto ( n  0) faça 
 início 
 se (n mod 2  0) então 
 início 
 r  r + m; 
 fim 
 n  n div 2; 
 m  m * 2; 
 fim 
 retorna r; 
fim 
módulo inteiro [] alg_II(inteiro A[][], inteiro n, 
inteiro chave) 
início 
 inteiro i, f, l, m; lógica achou; 
 para (i  0; i < n; i ++) faça 
 f  0; l  n-1; achou  falso; 
 enquanto((f <= l) e ( não achou)) faça 
 m  (f + l) div 2; 
 se (chave == A[i][m]) então 
 POS[i]  m; achou  verdadeiro; 
 senão se (chave < A[i][m]) então 
 l  m-1; 
 senão 
 f  m + 1; 
 fim-enquanto 
 se (não achou) então POS[i]  -1; 
 fim-para 
 retorna POS; 
fim. 
a) 
T(n) = n x( ⌊log2 𝑛⌋ + 1) = 
𝑛 ⌊log2 𝑛⌋ + 𝑛 
 
b) 
f(n) é O(g(n)) se  c  R+ e  n0  Z+ 
tal que 
 
f(n)  c g(n) , n  n0 
 
Então, seja g(n) = 𝑛 log2 𝑛 
 
𝑛 ⌊log2 𝑛⌋ + 𝑛  c 𝑛 log2 𝑛, n  n0 
 
fazendo c = 2 e n0 = 2 
 
𝑛 ⌊log2 𝑛⌋ + 𝑛  2 𝑛 log2 𝑛, n  2 
 
portanto, T(n) = O(𝑛 log2 𝑛). 
 
. 
 
Pede-se: 
a) Quais possíveis valores de n no pior caso e melhor caso? 
Pior caso: ocorre quando n é um valor ímpar e a divisão dos próximos valores 
continua ímpar. 
Melhor Caso: ocorre quando n é um valor par e a sua divisão por dois continua 
par. Vale comentar que, mesmo nesse caso, o condicional será verdadeiro 
quando n assume o valor 1. 
 
b) Qual a T(n), em termos de operações primitivas, no pior caso? 
 n 1 3 7 15 
 Total de vezes 2 3 4 5 
que repete n  0 
 
Logo, a função que melhor representa as repetições de n  0 é ⌊log2 𝑛 + 1⌋ +
 1 
 r  0; ----------------------------------------------------- 1 
 enquanto ( n  0) faça ------------------------------- ⌊log2 𝑛 + 1⌋ + 1 
 início 
 se (n mod 2  0) então 
 início 
 r  r + m; 8 * ⌊log2 𝑛 + 1⌋ 
 fim 
 n  n div 2; 
 m  m * 2; 
 fim 
 retorna r; ------------------------------------------------ 1 
Portanto, T(n) = 9 * ⌊log2 𝑛 + 1⌋ + 3 operações primitivas. 
 
c) Qual o  (Theta), por quê? 
 
Resposta: Pela definição sabe-se que, dada duas funções positivas f(n) e g(n), 
f(n) é (g(n)) se existem números ositivos c1, c2 e n0 tais que c1g(n)  f(n)  c2g(n) 
para todo n  n0. 
 
Então, fazendo g(n) = log2n, f(n) = t(n) 
 
 c1 log2n  9 * ⌊log2 𝑛 + 1⌋ + 3  c2 log2
n, para todo n  n0 
 
Obtém-se 
 c1 = 1, c2 = 15, para todo n  2. 
 
9) (Análise de Algoritmos Iterativos - Baseada no ENADE) No cálculo da 
potência de n elevado a n ( nn ), onde n pertence a N, é possível elaborar 
diferentes algoritmos. Em particular, pode-se pensar em soluções 
algorítmicas que calculam a potência para valores de n múltiplos de 2, tais 
como: 1, 2, 4, 8, 16, 32,... Duas soluções algorítmicas que calculam a 
potência para valores de n múltiplos de 2 são apresentados a seguir. 
 
Algoritmo 1: 
 
função inteiro n_elevado_n ( inteiro n ) 
início 
 inteiro res, i; 
 res ← 1; 
 para (i ← 1; i ≤ n; i++) façares ← res * n; 
 retorna res; 
fim. 
 
 
 
Algoritmo 2: 
 
função inteiro n_elevado_n2( inteiro n ) 
início 
 inteiro res, i; 
 res ← n 
 para (i ← 1; i < n; i= i * 2) faça 
 res ← res * res; 
 retorna res; 
fim. 
 
Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação 
proposta entre elas. 
I - O Algoritmo 1 é mais eficiente que o Algoritmo 2 em termos do tempo 
de execução. 
 PORQUÊ 
II - A complexidade assintótica do Algoritmo 1 é O(n log n) e do Algoritmo 
2 é O( n ). 
A respeito dessas asserções, assinale a alternativa correta. 
A) As asserções I e II são proposições verdadeiras, e a II é justificativa 
correta da I. 
B) As asserções I e II são proposições verdadeiras, mas a II não é uma 
justificativa correta da I. 
C) A asserção I é uma proposição verdadeira, e a II é uma proposição falsa. 
D) A asserção I é uma proposição falsa, e a II é uma proposição verdadeira. 
E) As asserções I e II são proposições falsas. 
 
Resposta: 
A alternativa correta é a “E”, pois a complexidade assintótica (pior caso) do Algoritmo 1 = O(n) 
e Algoritmo 2 = O(log n) , o que indica que o Algoritmo 2 é mais eficiente que o Algoritmo 1 em 
termos do tempo de execução. 
 
10) Um algoritmo de complexidade 8 * log2 n. Num certo computador, num tempo 
t, o algoritmo resolve um problema de tamanho 16 dados. Imagine agora que 
você tem disponível um computador 2 vezes mais rápido. Qual o tamanho 
máximo de problema que o mesmo algoritmo resolve no mesmo tempo t no 
computador mais rápido. 
 
Resposta: 
8 log2 16 ------ t 
8 log2 n ------ 2 t 
8 log2 n x t = 2 t x 8 log2 16 
log2 n = 2 x log2 16 
log2 n = 2 x 4 
2 8 = n 
n = 256 dados 
Resposta: O novo tamanho do problema é 256 dados 
11) Um certo professor criou um programa para levantar estatísticas sobre o 
desempenho de seus alunos. A eficiência do programa é medida pelo 
número de comparações feitas no processamento e é expressa pela função 
A(n) = n² + 500 – lg lg n, onde n é o número de alunos da turma. A direção 
da escola aprovou o uso do programa e resolveu aplicá-lo para todos os 
alunos. Outro professor gostou da ideia e resolveu criar o seu próprio 
programa com eficiência medida por B(n) = 60n - lg lg n. Agora é necessário 
saber qual dos dois programas será utilizado. De modo a auxiliar a direção 
da escola na tomada de decisão, calcule e determine qual valor de n  N a 
função A(n) é mais eficiente que B(n): 
 
Justificativa: 
Sejam as duas funções de eficiência dos programas A(n) =n2 + 500 - lg lg n e B(n) = 60n 
- lg lg n. 
 
Para que A(n) seja mais eficiente que B(n), A(n) < B(n). 
 
Montando a inequação: 
 
n2 + 500 - lg lg n < 60n - lg lg n 
 
n2 -60n + 500 < 0 
 
Para encontrar a solução, deve-se resolver a equação do 2o grau correspondente: 
 
A resolução da equação do 2o grau "an2 + bn + c = 0" é dada pela fórmula: 
 
 n = (-b +/- raiz (delta)) / 2 * a, onde delta = b * b - 4 * a * c. 
 
Como a = 1, b = -60, c = 500, o delta é: delta = 3600 - 4 x 500 = 1600. 
Então, raiz ( delta ) = 40. 
Assim, 
 
n = (60 +/- 40) / 2 
n1 = 50 
n2 = 10 
 
Analisando os valores da raiz pela inequação encontra-se a resposta: 10 < n < 50, n  
N. 
 
12) Um algoritmo é executado em 5 segundos para uma entrada de tamanho 
100. Se o algoritmo tem tempo de execução dado por T(n)=K n log n, quanto 
tempo em segundos, aproximadamente, ele levará, no mesmo computador, 
para uma entrada de tamanho 1000? 
 
Resposta: 
 
Basta resolver a correspondência: 
K 100* log 100 ==> 5s 
K 1000 * log 1000 ==> x 
Logo x=((K*1000*log 1000)*5)/(K*100*log 100)= 1000*3*5/100*2 = 75 s 
 
13) Dois algoritmos A e B tem a função de complexidade de tempo A(n) =n2 + 
500 + lg n e B(n) = 60n + lg n. Pergunta-se: Para quais n  N, A(n) é mais 
eficiente que B(n)? 
Resposta: 
A(n) =n2 + 500 + lg n e B(n) = 60n + lg n. 
 
A(n) < B(n) 
 
n2 + 500 + lg n < 60n + lg n 
 
n2 -60n + 500 < 0 
 
d = 3600 - 4 x 500 = 1600 = 40 
 
n = (60 +/- 40) / 2 
n1 = 50 
n2 = 10 
 
resposta : 10 < n < 50, n  N. 
 
14) Um algoritmo de complexidade 4* lg n. Num certo computador, num tempo t, 
o algoritmo resolve um problema de tamanho 32. Imagine agora que você 
tem disponível um computador 2 vezes mais rápido. Qual o tamanho máximo 
do problema que o mesmo algoritmo resolve no mesmo tempo t no 
computador mais rápido. 
 
Resposta: 
4 lg 32 ------ t 
4 lg n ------ 2 t 
 
4 lg n t = 4 lg 32 x 2 t 
 
lg n = lg 32 x 2 
 
lg n = 5 x 2 
 
2 10 = n 
 
n = 1024 dados 
 
 
15) Dois algoritmos A e B com complexidade A(n) =n2 + 500 - lg lg n e B(n) = 
60n - lg lg n. Pergunta-se: Para quais n  N, A(n) é mais eficiente que B(n)? 
 
Resposta: 
A(n) =n2 + 500 - lg lg n e B(n) = 60n - lg lg n. 
 
A(n) < B(n) 
 
n2 + 500 - lg lg n < 60n - lg lg n 
 
n2 -60n + 500 < 0 
 
d = 3600 - 4 x 500 = 1600 = 40 
 
n = (60 +/- 40) / 2 
n1 = 50 
n2 = 10 
 
resposta : 10 < n < 50, n  N. 
 
16) (Baseada nas questões do POSCOMP 2002 e 2004). Com base nos 
estudos sobre Notação Assintótica, determine quais das seguintes 
igualdades ou afirmações são verdadeiras. 
 
I. A propriedade transitividade é válida somente para as notações 
𝚯, 𝐎 𝐞 𝛀, mas não são válidas para as notações o e 𝛚. 
II. f(n) = O(g(n)) se e somente se g(n) = 𝛚 (f(n)) 
III. 𝐥𝐨𝐠𝟏𝟎 𝒏 + 𝒏 = 𝛀(𝐥𝐨𝐠𝟏𝟎 𝒏) 
IV. 𝟐𝒏+𝟑 = 𝐎(𝟐𝒏) 
V. √𝒏𝟑 + 𝐥𝐨𝐠𝟏𝟎 𝒏 = 𝚶(𝒏) 
A) somente II e IV 
B) somente I e III 
C) somente I e IV 
D) somente I, II e V 
E) somente III e IV 
 
Alternativa: E. 
Justificativa: 
I - Falsa, pois a propriedade de transitividade é válida para todas as notações 
assintóticas, conforme abaixo: 
f(n) = O(g(n)) e g(n) = O(h(n)) implicam f(n) = O(h(n)) 
f(n) = (g(n)) e g(n) = (h(n)) implicam f(n) = (h(n)) 
f(n) = (g(n)) e g(n) = (h(n)) implicam f(n) = (h(n)) 
f(n) = o(g(n)) e g(n) = o(h(n)) implicam f(n) = o(h(n)) 
f(n) = (g(n)) e g(n) = (h(n)) implicam f(n) = (h(n)). 
II - Falsa, pois a propriedade "Simetria de Transposição" descreve que "f(n) = O(g(n)) se 
e somente se g(n) = (f(n))". 
III - Verdadeira, pois a notação assintótica Ω é um limitante inferior e log10 𝑛 + 𝑛 >=
log10 𝑛. 
IV - Verdadeira, pois pela definição de O podemos encontrar g(n) = 2n. Para isso, basta 
fazer 8 ∗ 2𝑛 >= 2𝑛+3, 𝑝𝑎𝑟𝑎 𝑛 >= 1. 
V - Falsa, como √𝑛3 + log10 𝑛 >= 𝑛, 𝑛 não é um limitante superior para √𝑛3 +
 log10 𝑛, portanto √𝑛3 + log10 𝑛 = Ω(𝑛). 
 
17) Escrever se as afirmações abaixo são verdadeiras ou falsas? 
Explicar o porquê em cada caso. 
 
a) log2 𝑛 + √𝑛 = O(log2 𝑛) 
Falso, pois √𝑛 é limitante superior a log2 𝑛. Assim, log2 𝑛 + √𝑛 = O(√𝑛). 
 
b) 3𝑛+2 = Θ(3𝑛) 
Verdadeiro, pois 3𝑛+2 = 323𝑛 = 9 3𝑛. Pela definição de Theta. 
 
c1 3𝑛 ≤ 9 3𝑛 ≤ c2 3𝑛, n >= n0, fazendo c1 = c2 = 9 e n0 = 0. 
 
c) 1000n2 + n log2 𝑛
2 = Ω(𝑛2) 
Verdadeiro, pois um limitante inferior da função 1000 𝑛2 + 2 n log2 𝑛 pode ser 𝑛
2 
 
 
d) f(n) = (g(n)) se e somente se g(n) = O(f(n)) 
Falso, pois g(n) = n e g(n) = n, então n é O (n), mas f(n) = n não é (g(n) = n). 
 
e) n3 + n3 log2 n2 = o(n4) 
Verdadeiro, pois f(n) = n3 + n3 log2 n2 = n3 + 2 n3 log2 n é o(n4), ou seja 
lim
𝑛→ ∞
𝑛3+2 𝑛3 log2 𝑛
𝑛4
= 0. 
 
 
18) Quais das seguintes igualdades ou afirmações NÃO são 
verdadeiras? 
Explicar o por que em cada caso. 
 
I. A propriedade transitividade é válida somente para as notações Θ, O e Ω, 
mas não são válidas para as notações o e ω. 
FALSA. 
Segundo as propriedades estudadas, transitividade é aplicada a todas notações 
assintóticas, ou seja, f(n) = O(g(n)) e g(n) = O(h(n)) implicam f(n) = O(h(n)) 
f(n) = (g(n)) e g(n) = (h(n)) implicam f(n) = (h(n)) 
f(n) = (g(n)) e g(n) = (h(n)) implicam f(n) = (h(n)) 
f(n) = o(g(n)) e g(n) = o(h(n)) implicam f(n) = o(h(n)) 
f(n) = (g(n)) e g(n) = (h(n)) implicam f(n) = (h(n)) 
 
II. f(n) = O(g(n)) se e somente se g(n) = ω (f(n)) 
FALSA. 
Segundo apropriedade Simetria da Transposição, f(n) = O(g(n)) se e somente se g(n) = 
(f(n)). 
 
III. log10 𝑛 + 𝑛 = Ω(log10 𝑛) 
 
VERDADEIRO. 
Pela definição: Dada duas funções positivas f(n) e g(n), f(n) é (g(n)) se existem números 
positivos c e n0 tais que f(n)  cg(n) para todo n  n0. 
Assim, 
log10 𝑛 + 𝑛  c log10 𝑛 para todo n  n0 
Fazendo c = 1 e n0 = 1 
log10 𝑛 + 𝑛  log10 𝑛 para todo n  1 
Portanto, log10 𝑛 + 𝑛 = Ω(log10 𝑛) 
 
IV. 2𝑛+3 = O(2𝑛) 
 
VERDADEIRO. 
Pela definição: Dada duas funções positivas f(n) e g(n), f(n) é O(g(n)) se existem números 
positivos c e n0 tais que f(n)  cg(n) para todo n  n0. 
Assim, 
2𝑛+3  c 2𝑛 para todo n  n0 
Fazendo c = 8 e n0 = 0 
2𝑛+3  8 2𝑛 para todo n  0 
Portanto, 2𝑛+3 = O(2𝑛) 
 
 
V. √𝑛3 + log10 𝑛 = Ο(𝑛) 
FALSA. 
Pelas propriedades de O-grande 𝑛
3
2 + log10 𝑛 = O(𝑛
3
2) 
Portanto, √𝑛3 + log10 𝑛 𝑑𝑖𝑓𝑒𝑟𝑒𝑛𝑡𝑒 𝑑𝑒 Ο(𝑛) 
 
 
19) (Baseada em questão do POSCOMP 2016). Um algoritmo que trabalha com 
uma matriz A contendo n linha e m colunas tem complexidade O(100m4 + 
10m2n2 + 200mn2 + 800n2 + 90m2 ). Considerando as propriedades do O-
Grande, apresente uma maneira simplificada de expressar a complexidade 
desse algoritmo. 
A) O(m4 ). 
B) O(m2 ). 
C) O(m4 + m2n2 ). 
D) O(m2n2 ). 
E) O(m4+ n2 ). 
 
Resposta: Aplicando-se as propriedades de O-Grande, esta complexidade pode ser 
simplificada para: O(m4 + m2n2 ). Alternativa C. 
 
20) Sabendo-se que a função de complexidade obtida para um algoritmo no pior 
caso foi T(n) = 12n + 4. Determine o  (Theta) pela definição, ou seja, 
encontre c1, c2, n0 e a g(n). 
 
Resposta: A definição de Theta descreve: Dada duas funções positivas f(n) e g(n), f(n) é 
(g(n)) se existem números positivos c1, c2 e n0 tais que c1g(n)  f(n)  c2g(n) para todo 
n  n0. 
Logo, devemos encontrar g(n), c1, c2 e n0 tais que c1g(n)  f(n)  c2g(n) para todo n  n0. 
 c1g(n)  12n + 4  c2g(n) para todo n  n0. 
Considerando g(n) = n. 
 c1 n  12n + 4  c2 n para todo n  n0. 
Fazendo c1 = 1 e c2 = 16, n0 = 1, a expressão é validada para todo n  1. 
Portanto, f(n) = 12n + 4 é  (n). 
 
 
21) Qual o  (n) para t(n) = n2 - n - 2 ? Mostre pela definição de , encontrando 
as constantes, c1, c2 e n0. 
Resposta: Definição para  (n): Dada duas funções positivas f(n) e g(n), f(n) é 
(g(n)) se existem números positivos c1, c2 ( > 0 e  R+) e n0 tais que c1g(n)  
f(n)  c2g(n) para todo n  n0 (n0  0 e  Z+). 
 
para t(n) = n2 - n - 2 
 
Supondo g(n) = n2 
 
c1 n2 <= n2 - n - 2 <= c2 n2, n >= n0 
0,5 n2 <= n2 - n - 2 <= 2 n2, n >= 4 
 
encontramos c1 = 0,5, c2 = 2, n0 = 4. 
 
22) Considere T(n) = T(n) = 8n - 8, encontre o O-Grande para a função T(n) pela 
definição?. 
 
Resposta: 
Duas funções positivas f(n) e g(n), f(n) é O(g(n)) se existem duas constantes 
positivas c e n0 tal que f(n) <= c g(n), n >= n0 
Então, considerando g(n) = n 
8n-8 <= c n, n >=n0, fazendo c = 8 e n0 = 0, temos 
8n-8<= 8n, n>=0, portanto, T(n) é O(n). 
 
23) Sejam as funções f(n) = (lg n)3 + n e g(n) = n + n2 lg n. Compará-las e dizer 
se f(n) = O(g(n)), f(n)=Ω(g(n)) e/ou f(n) = Θ(g(n)), f(n) = o(g(n)) ou f(n) = 
(g(n)). 
 
Resposta: Sejam as funções 
f(n) = (lg n)3 + n 
e 
g(n) = n + n2 lg n. 
 
Compará-las e dizer se f(n) = O(g(n)), f(n)=Ω(g(n)) e/ou f(n) = Θ(g(n)), f(n) = 
o(g(n)) ou f(n) = (g(n)). (0.2) (Demonstre\explique sua solução, sem ela o 
exercício não será avaliado). 
 
Pelas propriedades 3, 4, 6, 7, 10 de O-Grande obtemos que: 
 
f(n) = (lg n)3 + n é O(n) 
 
g(n) = n + n2 lg n é O(n2 lg n) 
 
 
fazendo 
 
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= 0 
 
portanto f(n) é o(g(n) e, como g(n) é um limitante superior para f(n) satisfaz a 
definição de O-grande, portanto: f(n) é O(g(n)). 
 
24) Sejam as funções f(n) = (lg n)3 + n2 lg n e g(n) = n2 + n lg n. Compará-las e 
dizer se f(n) = O(g(n)), f(n)=Ω(g(n)) e/ou f(n) = Θ(g(n)), f(n) = o(g(n)) ou f(n) = 
(g(n)). 
Resposta: 
Sejam as funções 
 
f(n) = (lg n)3 + n2 lg n 
 
e 
 
g(n) = n2 + n lg n 
 
Compará-las e dizer se f(n) = O(g(n)), f(n)=Ω(g(n)) e/ou f(n) = Θ(g(n)), f(n) = 
o(g(n)) ou f(n) = (g(n)). (0.2) (Demonstre\explique sua solução, sem ela o 
exercício não será avaliado). 
 
Pelas propriedades 3, 4, 6, 7, 10 de O-Grande obtemos que: 
 
 
f(n) é O(n2 lg n) 
 
g(n) é O(n2) 
 
 
fazendo 
lim
𝑛→∞
𝑓(𝑛)
𝑔(𝑛)
= lim
𝑛→∞
𝑙𝑔 𝑛 =  
 
portanto f(n) é ω(g(n) e, como g(n) é um limitante inferior para f(n) também 
satisfaz a definição de Ω, portanto: f(n) é Ω (g(n)).