algorithmbig-oasymptotic-complexitylittle-o

Algorithms - Both Little o and Big Omega on the same functions?

I have two functions, f(n),g(n) such that f(n)=o(g(n)).

to be clear, I'm taking about little o

It is possible with that information given to me, that f(n)=Omega(g(n)).

To me it sounds that it's not possible, since Little-o definition says to me that 

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

Thanks!

Solution

  • Let's assume that both f and g are strictly positive.

    f(n) = o(g(n)) means f(n)/g(n) -> 0 as n tends to infinity.

    f(n) = Ω(g(n)) means (assuming the Knuth definition of Ω) g(n) = O(f(n)), which means there's a c>0 such that for large enough n, g(n) <= cf(n). But then, for large enough n, f(n)/g(n) >= 1/c > 0. So it's not possible that f(n)/g(n) -> 0 as n tends to infinity, which means that it's impossible that f(n) = Ω(g(n)) and f(n) = o(g(n)).