logic - Don't really understand the notation -
i don't understand how or i'm supposed prove. i've researched each, still unclear me expected.
which of following statements true? prove answers.
- n² ∈ o(n³)
- n² ∈ Ω(n³)
- 2ⁿ ∈ Θ(2n+1)
- n! ∈ Θ((n+1)!)
any appreciated!
since (probably homework) questions days old, think can answer question in short.
the wikipedia page (and textbook and/or notes too) says
f(n) ∈ o(g(n)) ⇔ lim sup |f(n)/g(n)| < ∞ f(n) ∈ Ω(g(n)) ⇔ lim sup |f(n)/g(n)| > 0 f(n) ∈ Θ(g(n)) ⇔ f(n) ∈ o(g(n)) , f(n) ∈ Ω(g(n))
to prove left side can prove right side.
n² ∈ o(n³)
true, due tolim sup |n²/n³| = lim (n²/n³) = lim (1/n) = 0 < ∞
n² ∈ Ω(n³)
false, due tolim sup |n²/n³| = lim (n²/n³) = lim (1/n) = 0
2ⁿ ∈ Θ(2n+1)
true, due to0 < lim sup |2ⁿ/2<sup>n+1</sup>| = lim (2ⁿ/(2⋅2ⁿ) = lim (1/2) = 1/2 < ∞
n! ∈ Θ((n+1)!)
false, due tolim sup |n!/(n+1)!| = lim (n!/((n+1)⋅n!) = lim (1/(n+1)) = 0
notice: limits holds n → ∞
.
Comments
Post a Comment