Не очень понимаю обозначения

Question

Я не очень понимаю, как или что я должен доказать. Я исследовал каждый из них, но мне все еще неясно, что ожидается.

Какие из следующих утверждений верны? Докажите свои ответы.

1. n² ∈ O (n³)
2. n² ∈ Ω (n³)
3. 2ⁿ ∈ Θ (2^{n + 1})
4. п! ∈ Θ((n+1)!)

Любая помощь приветствуется!

Answer 1

Поскольку этим (возможно, домашним) вопросам уже несколько дней, я думаю, что могу ответить на этот вопрос вкратце.

На странице википедии (и, надеюсь, ваш учебник и / или заметки тоже) написано

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)) and f(n) ∈ Ω(g(n))

Чтобы доказать левую сторону, вы можете доказать правую сторону.

1. n² ∈ O(n³) правда, из-за

   lim sup |n²/n³| = lim (n²/n³) = lim (1/n) = 0 < ∞
   

2. n² ∈ Ω(n³) ложно, из-за

   lim sup |n²/n³| = lim (n²/n³) = lim (1/n) = 0
   

3. 2ⁿ ∈ Θ(2n+1) правда, из-за

   0 < lim sup |2ⁿ/2<sup>n+1</sup>| = lim (2ⁿ/(2⋅2ⁿ) = lim (1/2) = 1/2 < ∞
   

4. n! ∈ Θ((n+1)!) ложно, из-за

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

Примечание: все ограничения действительны для n → ∞,