Big Oh и Omega доказательство сложности обозначений

Question

1. Докажите, что n³ не находится в O (n²)
2. Докажите, что n³ не входит в OMEGA (n⁴)

Answer 1

1. Предположим, что n³ находится в O(n²), тогда существует некоторая пара положительных постоянных c а также n₀ такой, что n³ ≤ cn² для всех n ≥ n₀, но для любой константы c это тривиально ложно, когда n > cТаким образом, мы имеем противоречие.

2. Предположим, что n³ находится в Ω(n⁴), тогда существует некоторая пара положительных постоянных. c а также n₀ такой, что n³ ≥ cn⁴ для всех n ≥ n₀, но для любой константы c, это тривиально ложно, когда n > max(1,1/c)Таким образом, мы имеем противоречие.