Big Omega

Text Material Preview

Big Omega 
O que representa a notacao Big Omega ()?
a) O limite superior de uma funcao assintotica.
b) O limite inferior de uma funcao assintotica.
c) A complexidade no pior caso de um algoritmo.
d) O comportamento medio de um algoritmo em termos de tempo de execucao.
Resposta correta: b) O limite inferior de uma funcao assintotica.
Explicacao: A notacao Big Omega () descreve o limite inferior do comportamento assintotico de
uma funcao, indicando que, em termos de complexidade, a funcao nao pode crescer mais devagar
do que uma certa taxa em um caso assintotico.
Como a notacao Big Omega () se relaciona com a Big O?
a) Ambas descrevem o mesmo tipo de comportamento assintotico, mas Big O e mais precisa.
b) Big Omega descreve o limite superior, enquanto Big O descreve o limite inferior.
c) Big O descreve o limite superior, enquanto Big Omega descreve o limite inferior.
d) Big Omega e Big O sao sinonimos e podem ser usadas de forma intercambiavel.
Resposta correta: c) Big O descreve o limite superior, enquanto Big Omega descreve o limite
inferior.
Explicacao: Big O fornece uma limitacao superior, ou seja, descreve o comportamento de uma
funcao no pior caso. Ja Big Omega fornece uma limitacao inferior, ou seja, descreve o
comportamento da funcao no melhor caso possivel.
Se uma funcao f(n) e (n2), o que isso significa?
a) f(n) cresce com uma taxa no minimo tao rapida quanto n2.
b) f(n) cresce com uma taxa maior do que n2.
c) f(n) e limitada superiormente por n2.
d) f(n) e limitada inferiormente por n2, mas nao necessariamente de forma precisa.
Resposta correta: a) f(n) cresce com uma taxa no minimo tao rapida quanto n2.
Explicacao: A notacao Big Omega () indica que a funcao nao pode crescer mais devagar do que a
taxa n2, ou seja, ela cresce pelo menos tao rapidamente quanto n2.
Qual e a diferenca principal entre Big Omega () e Big Theta ()?
a) Big Omega descreve limites superiores, enquanto Big Theta descreve apenas limites inferiores.
b) Big Omega fornece uma limitacao superior mais estrita do que Big Theta.
c) Big Theta descreve tanto limites superior quanto inferior, enquanto Big Omega descreve apenas
o limite inferior.
d) Big Omega e mais usada para analise de complexidade espacial de algoritmos.
Resposta correta: c) Big Theta descreve tanto limites superior quanto inferior, enquanto Big Omega
descreve apenas o limite inferior.
Explicacao: A notacao Big Omega () fornece uma descricao do limite inferior do comportamento
assintotico de uma funcao, enquanto Big Theta () descreve tanto os limites superior quanto inferior.
Dada a funcao f(n) = 4n2 + 3n, qual seria a notacao Big Omega () correta para f(n)?
a) (n)
b) (n2)
c) (n3)
d) (log n)
Resposta correta: b) (n2)
Explicacao: O termo dominante e 4n2, logo a funcao f(n) nao pode crescer mais lentamente do que
n2. A notacao correta e (n2).
O que significa dizer que f(n) = (n log n)?
a) f(n) tem uma taxa de crescimento maior ou igual a n log n.
b) f(n) tem uma taxa de crescimento menor ou igual a n log n.
c) f(n) nunca pode crescer mais rapido que n log n.
d) f(n) e uma funcao constante.
Resposta correta: a) f(n) tem uma taxa de crescimento maior ou igual a n log n.
Explicacao: A notacao (n log n) indica que a funcao f(n) cresce com uma taxa no minimo tao rapida
quanto n log n, ou seja, nao cresce mais devagar do que isso.
Se f(n) = 3n3 + 2n2 + n, qual seria a notacao Big Omega () para f(n)?
a) (n)
b) (n2)
c) (n3)
d) (n4)
Resposta correta: c) (n3)
Explicacao: O termo dominante em f(n) e 3n3, entao a funcao tem um crescimento assintotico que e
no minimo tao rapido quanto n3. A notacao correta e (n3).
Qual seria a notacao Big Omega para a funcao f(n) = 7n log n + 10n?
a) (n log n)
b) (n)
c) (n2)
d) (log n)
Resposta correta: a) (n log n)
Explicacao: O termo dominante em f(n) e 7n log n, portanto a taxa de crescimento e no minimo (n
log n), ja que o termo n log n cresce mais rapidamente que n.
Se uma funcao f(n) = 5n2 + 2n + 10, qual e a notacao Big Omega () 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 5n2. Isso significa que a funcao nao pode crescer mais
devagar que n2, ou seja, a notacao correta e (n2).
Dado f(n) = n log n + 5n, qual e a notacao Big Omega () dessa funcao?
a) (log n)
b) (n log n)
c) (n)
d) (n2)
Resposta correta: b) (n log n)
Explicacao: O termo dominante em f(n) e n log n, logo, a funcao tem uma taxa de crescimento no
minimo tao rapida quanto n log n.
Qual e a utilidade da notacao Big Omega () em analise de algoritmos?
a) Ela ajuda a determinar o tempo de execucao no pior caso.
b) Ela fornece uma estimativa para o tempo de execucao no melhor caso.
c) Ela e util para encontrar o limite superior de uma funcao.
d) Ela ajuda a determinar a eficiencia de um algoritmo considerando apenas o espaco de memoria.
Resposta correta: b) Ela fornece uma estimativa para o tempo de execucao no melhor caso.
Explicacao: A notacao Big Omega e util para descrever o limite inferior do comportamento de um
algoritmo, ou seja, o tempo de execucao no melhor caso.
Qual seria a notacao Big Omega para a funcao f(n) = 2n3 + 3n2 + 5?
a) (n)
b) (n2)
c) (n3)
d) (n4)
Resposta correta: c) (n3)
Explicacao: O termo dominante em f(n) e 2n3, portanto, a funcao tem um limite inferior de (n3).
Se f(n) = 3n2 + 4n + 2, qual e a notacao Big Omega () para f(n)?
a) (n)
b) (n2)
c) (n log n)
d) (n3)
Resposta correta: b) (n2)
Explicacao: O termo dominante em f(n) e 3n2, logo a funcao tem um limite inferior de (n2),
indicando que ela cresce com a taxa de n2 ou mais rapidamente.
Se f(n) = 2n log n + n, qual seria a notacao Big Omega () correta para f(n)?
a) (n)
b) (n log n)
c) (n2)
d) (log n)
Resposta correta: b) (n log n)
Explicacao: O termo dominante em f(n) e 2n log n, logo a funcao cresce no minimo com a taxa (n
log n).
Dada a funcao f(n) = 8n + 3, qual seria a notacao Big Omega para f(n)?
a) (n)
b) (log n)
c) (n2)
d) (n3)
Resposta correta: a) (n)
Explicacao: O termo dominante em f(n) e 8n, logo a funcao cresce com a taxa de n, e a notacao
correta e (n).
Qual seria a notacao Big Omega para uma funcao f(n) que tem uma taxa de crescimento inferior ou
igual a 2n3?
a) (n2)
b) (n log n)
c) (n3)
d) (log n)
Resposta correta: c) (n3)
**Exp