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.

  1. n² ∈ o(n³)
  2. n² ∈ Ω(n³)
  3. 2ⁿ ∈ Θ(2n+1)
  4. 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.

  1. n² ∈ o(n³) true, due to

    lim sup |n²/n³| = lim (n²/n³) = lim (1/n) = 0 < ∞ 
  2. n² ∈ Ω(n³) false, due to

    lim sup |n²/n³| = lim (n²/n³) = lim (1/n) = 0 
  3. 2ⁿ ∈ Θ(2n+1) true, due to

    0 < lim sup |2ⁿ/2<sup>n+1</sup>| = lim (2ⁿ/(2⋅2ⁿ) = lim (1/2) = 1/2 < ∞ 
  4. n! ∈ Θ((n+1)!) false, due to

    lim sup |n!/(n+1)!| = lim (n!/((n+1)⋅n!) = lim (1/(n+1)) = 0 

notice: limits holds n → ∞.


Comments

Popular posts from this blog

html - Firefox flex bug applied to buttons? -

html - Missing border-right in select on Firefox -

python - build a suggestions list using fuzzywuzzy -