Докажите или опровергните, что n³ = theta (n²)

Question

Я нашел следующую проблему на слайдах моего профессора без решения:

Докажите или опровергните, что n ³ = Θ (n ² )

Поэтому я попытался решить это сам.Но я не знаю, является ли мое решение правильным или нет, но я чувствую, что оно таково:

Нам нужно найти c ₁ , c ₂ и n ₀ так, что:

c ₁ ⋅g (n) ≤ f (n) ≤ c ₂ ⋅g (n)

Я обнаружил, что:

c ₁ *n ² ≤ n ³ ≤ c ₂ *n ²

и:

c ₁ = 1, c ₂ = 1, n ₀ = 1

Это правильно?

Answer 1

То, что вы написали, неверно,

C1 n² < n³ < C2 n²

можно упростить до

C1 < n < C2

, который не может удерживаться, поскольку n не ограничен (поэтому такого C2 нет).

Answer 2

Сказать, что f(n) = Theta(g(n)) равносильно тому, что f(n) = O(g(n)) and f(n) = Omega(g(n)).
Хотя правильно (и тривиально доказать), что n^3 = Omega(n^2) не содержит этого n^3 = O(n^2).
Доказательство:
Пусть c будет константой, нам нужно показать, что для всех n0 существует n > n0 st f(n) > cg(n) => n^3 > cn^2.
Fix n0, и путем выбора n = max(c, n0 + 1) > n0мы получаем n^3 = n*n^2 > c*n^2, завершая доказательство.