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

mysql - FireDac error 314 - but DLLs are in program directory -

git - How to list all releases of public repository with GitHub API V3 -

c++ - Getting C2512 "no default constructor" for `ClassA` error on the first parentheses of constructor for `ClassB`? -