CODEWITHSUNDEEP
time-complexitybig-ocomplexity-theory
kevin gu
kevin gu

Reputation: 11

Find the values for n0 and the constant factor c such that f(n) = n log n is Ω(n)

I was recently introduced to big O and big Omega, as well as big theta. I know that big O is the worse case scenario in terms of runtime, big Omega is the best case scenario, and big theta is in between. However, I'm still confused on how I would use it mathematically to prove that n log n = Ω(n). Also, I get that n0 is the lowest possible number for the equation to work, but where does the constant factor c come in? Any advice and help is greatly appreciated, thanks!

Upvotes: 1

Views: 465

Answers (2)

NANDINI KAUSHAL
NANDINI KAUSHAL

Reputation: 1

As mentioned in the definition of big-Ω,

we can say if the function f(n) is having growth rate faster than that of g(n) , f(n) = Ω(g(n))

Here n log n always grows faster than n Hence, n log n = Ω(n).

Upvotes: 0

Berthur
Berthur

Reputation: 4495

If you understand the definition of big-O, but struggle with the definition of big-Ω, you can use Knuth's definition of big-Ω to turn it around for you:

f(n) = Ω(n) <=> n = O(f(n))

Thus, if you can prove that n = O(n logn), you have proven your original problem.

If you are looking to understand the c and n0 defnition of big-Ω, I'm sure there are examples online. As already noted, see cs.stackexchange.com and math.stackexchange.com.

Upvotes: 0

Related Questions