Алгоритмы - и Little o, и Big Omega с одинаковыми функциями?

Question

У меня есть две функции, f(n),g(n) такой, что f(n)=o(g(n)),

чтобы быть ясно, я беру немного о

Возможно, с этой информацией, предоставленной мне, что f(n)=Omega(g(n)),

Мне кажется, что это невозможно, поскольку определение Литтл-о говорит мне, что

for every c>0,f(n)<c * g(n).

Спасибо!

Answer 1

Предположим, что f и g строго положительны.

f (n) = o (g (n)) означает f(n)/g(n) -> 0, так как n стремится к бесконечности.

f(n) = Ω(g(n)) означает (при условии определения Ω по Кнуту) g (n) = O (f (n)), что означает, что a c>0 такое, что для достаточно больших n, g(n) <= cf(n). Но тогда, при достаточно большом n, f(n)/g(n) >= 1/c > 0. Поэтому невозможно, чтобы f(n)/g(n) -> 0, когда n стремится к бесконечности, что означает что невозможно, чтобы f(n) = Ω(g(n)) и f (n) = o (g (n)).

Answer 2

Нет, это не гарантирует этого. Иногда большой O такой же, как у Omega(g(n)), но не всегда.