Формула Big Theta Notation сбивает с толку необходимость ясности

Question

Если математическое правило для обозначения большой тэты:

f(n) = Theta (g(n)) if and only if f(n) &gt= cg(n) for some c after n &gt= n<sub>0</sub> &gt=0

тогда, когда f (n) = 5n ² , тогда мы рассматриваем его как тета (n ² )
С учетом 5n ² > = n ² для c = 1 и n ₀ = 0
Но
Почему не F (N) = тета (N)
Учитывая 5n ² > = n для c = 1 и n ₀ = 0 ??

Answer 1

Прежде всего, Theta(g) - это набор функций. Технически, вам нужно написать f in Theta(g), а не f = Theta(g).

Неофициально Theta(g) содержит все функции, которые становятся одинаково сильными (асимптотически). Так что это похоже на асимптотику = (равно).

Некоторые f находятся в Theta(g), если они находятся в O(g) и Omega(g) одновременно.

---

Теперь к вашему примеру. У нас есть f(n) = 5n^2. Как вы сказали, это в Theta(n^2) Но это , а не в Theta(n). Ваш пример был c = 1 и n_0 = 0.

На данный момент ваша формула неверна . Определение Big-O

То есть с <=, а не с >=, это будет Big-Omega.

Получаем

5n^2 <= 1 * n

для ваших значений, давайте построим это для всех n >= n_0 = 0:

Как видно, f есть не меньше 1 * g для всех n >= n_0. Таким образом, это не в O(n).

А так как Theta означает оба, O и Omega, вы не можете быть в Theta, если вы не в O.