Я не понимаю, как правильно представить этот контрпример. Он не удовлетворяет ? (?) = ? (? (?)), так как ? (?) не является ? (? (?)). ? (?) = ω (? (?)), если f (n) равно 2n, а g (n) равно n.
Так как можно просто «Пусть Let (?) = 2? и ?(?) = ?. "
Но f (n) = 2n IS O (g (n)) для g (n) = n. Пусть n0 = 1 и c = 3. Тогда:
f(n) = 2n <= 3n = 3 * n = c * n = c * g(n), for n >= n0
Следовательно, контрпример действителен.
