Алгоритмы и структуры данных?

Question

[Rustam2002]

Объясните пожалуйста почему множество Тета принадлежит множеству О, а не наоборот ?

Answer 1

[Сергей Соловьев]

"... поскольку Тета обозначения более сильные чем О обозначения..."
Ответ кроется тут. Тета - более ограниченное множество, чем О, т.к. есть ограничение снизу:
- Тета = g1(n) <= f(n) <= g2(n)
- О = 0 <= f(n) <= g2(n)

Можешь заметить вот этот промежуток [0; g1(n)]. Это и есть разница между тета и О.
Таким образом, Тета меньше чем О, поэтому не может быть надмножеством. Ну а так как верхняя граница одинакова, то можно сказать, что О = Тета + [0; g1(n)]

Comments

[Rustam2002]

Спасибо большое