0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

$\log(n) \ge 1$ for any $n>2$. Hence, if we choose $n_0=2$, then for any $n>n_0$ we have $n\log(n)\ge n\cdot 1 = n$. Thus, by the definition of $\Omega$, we have that $n\log(n) = \Omega(n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.