CODEWITHSUNDEEP
big-ocomplexity-theory
NotSure
NotSure

Reputation: 681

comparing 2 functions with big O notation

The question is :

Assume that f, g: N → N are functions such that f(n)=O(logn) and g(n) = Ω(nlogn). Is it possible that f(n) = Ω(g(n))?

I'm thinking that it is not possible becaouse nlogn > logn, not sure if it's true nor how to proove it.

Thanks in advance !

Upvotes: 5

Views: 1000

Answers (1)

SomeWittyUsername
SomeWittyUsername

Reputation: 18348

No, it's not possible.

Let's assume it's possible:

  • g(n) = Ω(nlogn) ==> there is a such that g(n) > anlogn for a sufficiently large n.
  • f(n) = Ω(g(n)) ==> there is b such that f(n) > bg(n) > banlogn for a sufficiently large n.
  • Let c = ab ==> f(n) > cnlogn for a sufficiently large n ==> f(n) = Ω(nlogn).
  • f(n) = O(logn) ==> there is d such that f(n) < dlogn for a sufficiently large n.
  • ==> cnlogn < f(n) < dlogn ==> cnlogn < dlogn ==> n < d/c. That's not possible since natural number n exists which is larger than d/c. ==> contradiction to the initial assumption.

Upvotes: 3

Related Questions