Big Theta

Text Material Preview

Big Theta 
O que representa a notacao Big Theta ()?
a) A complexidade pior de um algoritmo.
b) O limite inferior de uma funcao assintotica.
c) O limite superior de uma funcao assintotica.
d) O comportamento assintotico de uma funcao em termos de sua taxa de crescimento.
Resposta correta: d) O comportamento assintotico de uma funcao em termos de sua taxa de
crescimento.
Explicacao: A notacao Big Theta () descreve o crescimento assintotico de uma funcao, fornecendo
uma descricao precisa da taxa de crescimento, tanto no limite superior quanto inferior.
Qual e a principal diferenca entre Big O e Big Theta?
a) Big O define o limite inferior, enquanto Big Theta define o limite superior.
b) Big O e usado apenas para algoritmos, enquanto Big Theta e usado para qualquer tipo de
funcao.
c) Big O fornece uma descricao mais precisa do comportamento assintotico do que Big Theta.
d) Big Theta descreve uma funcao de forma mais precisa, considerando tanto o limite superior
quanto inferior.
Resposta correta: d) Big Theta descreve uma funcao de forma mais precisa, considerando tanto o
limite superior quanto inferior.
Explicacao: A notacao Big Theta () fornece uma analise mais precisa do comportamento
assintotico, pois limita a funcao tanto pelo seu limite superior quanto inferior, enquanto Big O
apenas faz uma limitacao superior.
Qual das seguintes afirmacoes sobre a notacao Big Theta e verdadeira?
a) A notacao Big Theta pode ser usada para descrever a complexidade espacial de um algoritmo.
b) Big Theta pode ser usado para descrever apenas algoritmos de ordenacao.
c) Big Theta indica que uma funcao tem uma taxa de crescimento que e no minimo e no maximo de
uma certa ordem.
d) Big Theta so pode ser usada para funcoes lineares.
Resposta correta: c) Big Theta indica que uma funcao tem uma taxa de crescimento que e no
minimo e no maximo de uma certa ordem.
Explicacao: A notacao Big Theta descreve o comportamento assintotico de uma funcao, indicando
que a funcao cresce dentro de certos limites, tanto superior quanto inferior.
Se f(n) = 3n2 + 5n + 7, qual e a notacao Big Theta correta para f(n)?
a) (n)
b) (n2)
c) (n3)
d) (n log n)
Resposta correta: b) (n2)
Explicacao: O termo dominante em f(n) e 3n2, portanto, a complexidade assintotica e (n2).
Qual e a relacao entre Big Theta () e Big Omega ()?
a) Big Theta e uma forma de Big Omega, mas com um limite superior mais estrito.
b) Big Theta descreve limites superiores, enquanto Big Omega descreve limites inferiores.
c) Big Omega descreve limites superiores, enquanto Big Theta descreve limites inferiores.
d) Big Theta e Big Omega sao formas equivalentes de descrever a complexidade assintotica de
uma funcao.
Resposta correta: b) Big Theta descreve limites superiores, enquanto Big Omega descreve limites
inferiores.
Explicacao: A notacao Big Theta fornece uma descricao completa, com limites superior e inferior,
enquanto Big Omega apenas fornece um limite inferior para a taxa de crescimento de uma funcao.
Se f(n) = 4n3 + 2n2 + n, qual e a notacao Big Theta para f(n)?
a) (n)
b) (n2)
c) (n3)
d) (n4)
Resposta correta: c) (n3)
Explicacao: O termo dominante em f(n) e 4n3, logo a complexidade assintotica e (n3).
Qual das alternativas abaixo e a melhor descricao do comportamento assintotico de uma funcao
f(n) = 5n2 + 3n + 1 quando n e grande?
a) f(n) = (n)
b) f(n) = (n2)
c) f(n) = (n3)
d) f(n) = (log n)
Resposta correta: b) f(n) = (n2)
Explicacao: Quando n e grande, o termo dominante de f(n) e 5n2, entao a funcao tem uma
complexidade de (n2).
Em qual das seguintes situacoes seria mais apropriado usar a notacao Big Theta ()?
a) Quando se deseja descrever a complexidade no pior caso de um algoritmo.
b) Quando se deseja uma estimativa mais precisa da complexidade assintotica, considerando tanto
os limites superior quanto inferior.
c) Quando se deseja descrever apenas o melhor caso de um algoritmo.
d) Quando se deseja avaliar o espaco de memoria consumido por um algoritmo.
Resposta correta: b) Quando se deseja uma estimativa mais precisa da complexidade assintotica,
considerando tanto os limites superior quanto inferior.
Explicacao: Big Theta () e a notacao que descreve uma funcao com precisao, considerando ambos
os limites, superior e inferior, da taxa de crescimento.
Se uma funcao f(n) e descrita como (n log n), qual seria o comportamento assintotico dessa
funcao?
a) Ela cresce mais lentamente que uma funcao linear.
b) Ela cresce mais rapidamente que uma funcao quadratica.
c) Ela cresce mais rapidamente que uma funcao linear, mas mais lentamente que uma funcao
quadratica.
d) Ela cresce de forma exponencial.
Resposta correta: c) Ela cresce mais rapidamente que uma funcao linear, mas mais lentamente que
uma funcao quadratica.
Explicacao: A funcao (n log n) e uma taxa de crescimento que cresce mais rapido que uma funcao
linear ((n)) mas mais devagar que uma funcao quadratica ((n2)).
Dado que f(n) = 2n3 + 4n2 + n, qual seria a notacao Big Theta para a funcao f(n)?
a) (n2)
b) (n3)
c) (n4)
d) (n)
Resposta correta: b) (n3)
Explicacao: O termo dominante em f(n) e 2n3, portanto a funcao cresce com a taxa (n3).
Qual das seguintes afirmacoes sobre a notacao Big Theta e verdadeira?
a) A notacao Big Theta so pode ser aplicada a funcoes polinomiais.
b) A notacao Big Theta fornece um limite superior estrito para uma funcao assintotica.
c) A notacao Big Theta e usada para descrever uma funcao com limites superior e inferior de sua
taxa de crescimento.
d) A notacao Big Theta e apenas usada para analise de algoritmos em tempo de execucao.
Resposta correta: c) A notacao Big Theta e usada para descrever uma funcao com limites superior
e inferior de sua taxa de crescimento.
Explicacao: A notacao Big Theta descreve de forma completa o comportamento assintotico de uma
funcao, limitando tanto superior quanto inferiormente.
Qual seria a notacao Big Theta para f(n) = 3n log n + 7n?
a) (n)
b) (n log n)
c) (n2)
d) (log n)
Resposta correta: b) (n log n)
Explicacao: O termo dominante e 3n log n, logo a complexidade assintotica de f(n) e (n log n).
Se f(n) = n + 2 log n, qual seria a notacao Big Theta para f(n)?
a) (log n)
b) (n)
c) (n log n)
d) (n2)
Resposta correta: b) (n)
Explicacao: O termo n cresce mais rapidamente do que o termo log n a medida que n aumenta,
portanto a complexidade assintotica e (n).
Qual e o impacto da notacao Big Theta na analise de algoritmos?
a) Ela ajuda a prever o tempo de execucao para entradas pequenas.
b) Ela fornece uma descricao precisa da taxa de crescimento de um algoritmo, considerando limites
superior e inferior.
c) Ela so e util para algoritmos que envolvem grandes conjuntos de dados.
d) Ela descreve apenas a complexidade de espaco dos algoritmos.
Resposta correta: b) Ela fornece uma descricao precisa da taxa de crescimento de um algoritmo,
considerando limites superior e inferior.
Explicacao: Big Theta oferece uma descricao precisa do crescimento assintotico de um algoritmo,
refletindo tanto os limites superior quanto inferior.
Qual seria a notacao Big Theta para a funcao f(n) = n2 + 10n + 5?
a) (n)
b) (n log n)
c) (n2)
d) (n3)
Resposta correta: c) (n2)
Explicacao: O termo dominante em f(n) e n2, portanto a notacao correta e (n2).