0

I need to prove or disprove $n\log_2(n)-3n-18 = \Omega(n)$ and get appropriate constants so that the lower bound limit definition is fulfilled.

My attempt In order to prove that relation, I use the notion of limit:

$$\lim_{n \to \infty} \frac{n\log_2(n)-3n-18}{n} = \left[\frac{\infty}{\infty}\right]$$

so applying L'Hôpital theorem and deriving numerator and denominator, I get

$$\lim_{n\to \infty} \frac{\log_2n+\dfrac{n}{n\log2}-3}{1} = \infty $$

so at this point I know that $n\log_2(n)-3n-18 = \omega(n)$... and that's where I get stuck and basically try to guess, so I am wondering if I can calculate the values I need: how do I select $c$ and $n_0$ so that $\exists c > 0$, $n_0 > 0$ such that $\forall n \geq n_0$, $f(n) \geq c\cdot g(n) \geq 0$?

haunted85
  • 1,418
  • 2
    so at this point I know that $n\log_2(n)-3n-18=o(n)$ No. You proved that it was $\omega(n)$ (which implies $\Omega(n)$), certainly not $o(n)$ (which is false and would be incompatible with $\Omega(n)$). – Clement C. Sep 26 '16 at 11:16
  • Opps... you're absolutely right, typo! – haunted85 Sep 26 '16 at 11:19

1 Answers1

0

You may want to show that for $n$ "big enough" you have $n \log_2 n - 3n -18 \geq n$. Note that for $n\geq 36$, we certainly have $\frac{1}{2}n \log_2 n \geq 18$, so it suffices to find $n_0\geq 36$ such that $$ \frac{1}{2}n\log_2 n - 3n \geq n $$ i.e. $$ n\log_2 n \geq 8n. $$ You should be able to do so easily.

Once you have this $n_0\geq 36$, you get that $$ n \log_2 n - 3n -18 \geq \frac{1}{2}n\log_2 n + 18 - 3n -18 = \frac{1}{2}n\log_2 n -3n \geq n $$ for all $n\geq n_0$, which shows what you want we constant $c=1$.

Note however that you then show $f(n)=\Omega(n)$ (with a tedious approach), while your direct limit argument immediately establishes the stronger $f(n)=\omega(n)$. The "find a constant and $n_0$ approach" is definitely not the simplest or most effective...

Clement C.
  • 67,323
  • Thank you for your answer. Can I ask how have you come up with 36? – haunted85 Sep 26 '16 at 11:32
  • I wanted to deal with the 18 in a simple way, while still leaving room for the $3n$. So I naively decided to "allocate" half of the leading term to both, and that leaves me with getting the inequality $\frac12n\log n \geq 18$. – Clement C. Sep 26 '16 at 11:46