O Notation

minkcy

2010-04-14 2:22 am

Hi, i don't know how to do the question below, can u please help?
Thank you!

1.For f ∈ O(n^2), which one is correct?
a) f ∈ O(n^4)
b) f might be in O(n^4)
c) f ∈/(not) O(n^4)

and if the answer is b) show example of f ∈ O(n^4) and f ∈/ O(n^4)

2.For f ∈ Θ(n^3), which one is correct?
a) f ∈ Θ(n^2)
b) f might be in Θ(n^2)
c) f ∈/(not) Θ(n^2)

and if the answer is b) show example of f ∈ Θ(n^2) and f ∈/ Θ(n^2)

2.For f ∈ Ω(n log n), which one is correct?
a) f ∈ Ω(n^3)
b) f might be in Ω(n^3)
c) f ∈/(not) Ω(n^3)

and and if the answer is b) show example of f ∈ Ω(n^3) and f ∈/ Ω(n^3)

回答 (1)

myisland8132

2010-04-14 5:46 am

✔ 最佳答案

1 f ∈ O(n^2)
|f|<=kn^2 for sufficiently large n
|f|<=kn^4 for sufficiently large n
ANSWER: A

2 f ∈ Θ(n^3)
k1 n^3 <= |f| <= k2 n^3 for sufficiently large n. So f should be a cubic polynomial.

ANSWER: C

3 f ∈ Ω(n log n),
|f| >=k n log n for sufficiently large n

If f is n^2, then f ∈/(not) Ω(n^3). However, if f is n^4, then ∈ Ω(n^3)
So the answer is B

👍 0 👎 0