Proving $\Omega$ Notation

Question

Prove the following:

$$ \frac{n^2}{4} \log ^2 \left(\frac{n}{4}\right) = \Omega \left(\frac{n^2}{2} \log ^2 \left(\frac{n}{2}\right)\right)$$

Whatever I try to do gets me nowhere, I tried multiplying both sides by $\dfrac{2}{n^2}$ and got to the inequality: $$\frac{\log^2 (\frac{n}{4})}{\log^2 (\frac{n}{2})} \geq 2c$$ $$\frac{(\log n-2)^2}{(\log n-1)^2} \geq 2c$$

But that leads me nowhere.

When you prove something you should start by one side and end by the other. — Mohammad, Jan 13 '14 at 18:01
@user689, but I need to find intuition for choosing the $n_0, c > 0$ for the $\Omega$ notation proof — Georgey, Jan 13 '14 at 18:02
I'm not sure I got you @Alex, what do you mean by integer part? — Georgey, Jan 13 '14 at 18:04
@Alex, oh no no, sorry, those are regular brackets. I just didn't want people to get confused with all of the brackets in the omega side. I know what it means, just not in English :) — Georgey, Jan 13 '14 at 18:06
@Alex, mind the denominator is 4 on the LHS and 2 on the RHS — Georgey, Jan 13 '14 at 18:10
Are you familiar with the theorem using limits for these kind of proofs? Or do you have to use the definition? — Code-Guru, Jan 13 '14 at 18:21
@Code-Guru, I am familiar with the limits theorem, but sadly I was supposed to use the definition. — Georgey, Jan 13 '14 at 18:27

score 0 · Accepted Answer · answered Jan 13 '14 at 18:40

0

Denote for simplicity $\log n =t$. From your last expression we need to find for what $t$ this holds. Solve the inequality $$ (1-2 c_1) t^2 +(4c_1-2)t +4 -2 c_1 \geq 0 $$ and select the positive root

answered Jan 13 '14 at 18:40

Alex

19,262

I solved it in another way, by simplifying LHS and then making it smaller (which is legit in omega proofs) to the stage where I could simply equate both LHS and RHS with some limitations on $n$. – Georgey Jan 14 '14 at 09:43

Proving $\Omega$ Notation

1 Answers1