Как доказать разницу между O (1) и Θ (1)?

Question

Я ссылался В чем разница между O (1) и Θ (1)? за то же самое.Но я не мог понять его математическую разницу.

Answer 1

f(x) = 1/x равно O(1), но не Θ(1).

Из книги CLRS:

O(g(n)) = {f(n): существует положительная постоянная c и n0 такая, что 0 <= f(n) <= c*g(n) для всех n >= n0}.

Θ(g(n)) = {f(n): существуют положительные константы c1, c2 и n0, такие что 0 <= c1*g(n) <= f(n) <= c2*g(n) для всех n >= n0}.

Здесь g(n) равно 1. И для 1/x вы не можете найти положительное c1, чтобы удовлетворить c1 <= 1/x при x -> бесконечности.