1
$\begingroup$

I'm having some trouble trying to prove $\log_{2}(n) \neq \Omega(\sqrt{n})$. I'm trying to do this without using limits.

I am able to prove $n^2 \neq \Omega(2^n)$, so if $\log_{2}(n)=\Omega(\sqrt{n}) \Rightarrow n^2 = \Omega(2^n)$ then I think I can use the contrapositive to disprove $\log_{2}(n) = \Omega(\sqrt{n})$.

The reason I think $\log_{2}(n)=\Omega(\sqrt{n}) $ implies $ n^2 = \Omega(2^n)$ is because $\log_{2}{n}$ has an integer solution $k$ at every $n=2^k$ while $\sqrt{n}$ has an integer solution $k$ at every $n=k^2$. So for $\log_{2}{n}$ to be in $\Omega(\sqrt{n})$, the distance between integer solutions for $\sqrt{n}$ would have to grow more quickly than the distance between integer solutions for $\log_{2}{n}$.

Is my reasoning valid?

Edit:

To prove that $n^2 \neq \Omega(2^n)$, I first assume it is true. So I assume the following is true:

$$\exists c \exists n_0 \forall n(n > n_0 \to n^2 \geq c \cdot 2^n)$$

Then I move the pieces of the inequality around a bit,

$$n^2 \geq c \cdot 2^n \Rightarrow 2\log{n} \geq \log{c} + n \Rightarrow 2 \geq \frac{\log{c}}{\log{n}} + \frac{n}{\log{n}}$$

So $(n > n_0) \to (2 \geq \frac{\log{c}}{\log{n}} + \frac{n}{\log{n}})$

I let $a = \max(2^{6-\log{c}}, c, n_0) + 7$, and $b=(a+3)^2$. Therefore, $b > a > n_0$, so the following should be true:

$$2 \geq \frac{\log{c}}{\log{b}} + \frac{b}{\log{b}}$$

To show that it is not true, I do the following:

For $0 < c < 1$: $$(\log{c} < 0) \land (\log{b} > 0) \land (|\log{b}| > |\log{c}|) \to -1 < \frac{\log{c}}{\log{b}} < 0$$

For $c \geq 1$:

$$(b > c) \to (\log{b} > \log{c}) \to 0 \leq \frac{\log{c}}{\log{b}} < 1$$

Therefore, for $c > 0$:

$$-1 < \frac{\log{c}}{\log{b}} < 1$$

Which means that:

$$-1 + \frac{b}{\log{b}} < \frac{\log{c}}{\log{b}} + \frac{b}{\log{b}} < 1 + \frac{b}{\log{b}}$$

Therefore, the following should be true:

$$2 \geq \frac{\log{c}}{\log{b}} + \frac{b}{\log{b}} > -1 + \frac{b}{\log{b}}$$

So I move the pieces of the inequality around a bit:

$$2 > -1 + \frac{b}{\log{b}} \Rightarrow 3 > \frac{b}{\log{b}} \Rightarrow 3 > \frac{(a+3)^2}{2\log{(a+3)}} \Rightarrow 6\log{(a+3)} > (a+3)^2$$

and remember that by the definition I gave for $a$,

$$(a+3 > 6) \land (a+3 > \log{a+3} > 1)$$

So it leads to a contradiction, as it is impossible for

$$6\log{(a+3)} > (a+3)^2$$

to be true.

Therefore, $n^2 \neq \Omega(2^n)$.

Edit 2: I used the inequality that Gary provided to prove that $\log{n} \neq \Omega(\sqrt{n})$:

$$\log{n} = \Omega(\sqrt{n}) \to \exists c \exists n_0 \forall n (n > n_0 \to \log{n} \geq c \cdot \sqrt{n})$$

$$\log{n} \geq c \cdot \sqrt{n} \Rightarrow \frac{\log{n}}{n^{1/2}} \geq c$$

$$\frac{\log{n}}{n^{1/2}} \leq \frac{4}{\ln{2} \cdot n^{1/4}} \textrm{, so}$$

$$ \frac{4}{\ln{2} \cdot n^{1/4}} \geq c \Rightarrow 4 \geq c \cdot \ln{2} \cdot n^{1/4} \textrm{ should be true.}$$

$$(\frac{1}{2} < \ln{2}) \to (c \cdot \frac{1}{2} \cdot n^{1/4} < c \cdot \ln2 \cdot n^{1/4})$$

$$4 \geq \frac{1}{2} \cdot c \cdot n^{1/4} \Rightarrow 8 \geq c \cdot n^{1/4}$$

$$\textrm{Let } a = \max\left(\left(\frac{8}{c^{-1}}\right)^4 + 1, c, n_0\right)+8^4$$

$$a > n_0 \textrm{, so } 8 \geq c \cdot a^{1/4} \textrm{ should be true but} $$

$$(0 < c < 1) \to (c \cdot \frac{8}{c^{-1}} = 8 \land a^{1/4} > \frac{8}{c^-1}) \to (c \cdot a^{1/4} > 8)$$

$$(c \geq 1) \to (a > 8^4) \to (c \cdot a ^{1/4} > 8)$$

$$\textrm{So } 8 \geq c \cdot a^{1/4} \textrm{ cannot be true}$$

Therefore, this leads to a contradiction so $\log{n} \neq \Omega(\sqrt{n})$.

$\endgroup$
6
  • 1
    $\begingroup$ You do not need limits, just notice that $$ 0 < \frac{{\log _2 n}}{{\sqrt n }} = \frac{1}{{\sqrt n }}\frac{{\log n}}{{\log 2}} = \frac{1}{{\sqrt n }}\frac{{4\log n^{1/4} }}{{\log 2}} \le \frac{1}{{\sqrt n }}\frac{4}{{\log 2}}n^{1/4} = \frac{4}{{\log 2}}\frac{1}{{n^{1/4} }}. $$ Thus, $\frac{{\log _2 n}}{{\sqrt n }}$ will eventually be less than any positive number. $\endgroup$
    – Gary
    Commented Feb 10, 2022 at 5:29
  • $\begingroup$ Can you add to question how you proof $n^2 \neq \Omega(2^n)$ ? $\endgroup$
    – zkutch
    Commented Feb 10, 2022 at 5:53
  • $\begingroup$ @zkutch I used a proof by contradiction. I let $n^2 = \Omega(2^n)$ be true, so $\exists c \exists n_0 \forall n (n > n_0 \to n^2 \geq c \cdot 2^n)$. Then I showed this cannot be the case because if you let $a = \max(2^{6-\log{c}}, c, n_0) + 7$ and $b=(a + 3)^2$, then $b > a > n_0$ so $b^2 \geq c \cdot 2^b$ should be true but it is not. $\endgroup$ Commented Feb 10, 2022 at 6:07
  • $\begingroup$ @zkutch I've undeleted the question $\endgroup$ Commented Feb 10, 2022 at 16:49
  • $\begingroup$ Why would you expect anything beyond $\log_2(n) = \Omega(\sqrt{n}) \implies n^2 = \Omega(2^{2 \sqrt{n}})? $ You're not applying the same function to both sides when you compare $n^2$ and $2^n$. Also, It doesn't hold in general that if $a_n = \Omega(b_n)$ then $\exp(a_n) = \Omega(\exp(b_n))$ - e.g. $a_n = n/2, b_n = n$. The best you can hope for is $\exp(\Omega(b_n))$ (which is not the same thing - why?) and this does hold if $a_n \to \infty$ - basically, there is some $c$ such that $a_n > cb_n$ for large enough $n$, and so $a_n - cb_n/2 \to \infty,$ and so does the exponent. $\endgroup$ Commented Feb 11, 2022 at 3:24

1 Answer 1

1
$\begingroup$

Taking negation in $O,\Omega, \Theta$ asymptotic notations needs good understanding when we are searching for values and when we have arbitrary variables. Such words as "quick" or "slow" should have exact mathematical understanding.

For example, let's compare $n \in O(2^n)$ to $n \notin \Omega(2^n)$.

For first we have $$\exists C>0,\exists N\in\mathbb{N}, \forall n > N, n \leqslant C \cdot 2^n\quad\quad(1)$$ For second $$\forall C>0,\forall N\in\mathbb{N}, \exists n > N, n < C \cdot 2^n\quad\quad(2)$$

We see, that while in first $(1)$ we are searching for $C$, then in second $(2)$ $C$ is arbitrary variable.

For $(1)$ is enough to know inequality $$n < 2^n, n\in \mathbb{N}\quad\quad(3)$$ Based on it we can use pair $C=1,N=1$.

But quite different is situation in $(2)$. Here $(3)$ type inequalities is not enough. Rewriting $(2)$ as $\frac{n}{2^n}<C$ where the statement of the problem is in finding $n$ for any $C>0$, we arrive at task similar to limit. When we decide to prove $(2)$, then usually we are using ways which, de facto, gives limit.

So, most easy is to use statement $\frac{n}{2^n}\to 0, n\to\infty$, which, of course, is more strong, then $(2)$. To argue with me, it will be quite suitable if someone can bring proof, which gives exactly $(2)$, but is not equivalent to limit.

And, at end, about your proof by contradiction in comment. Do I correctly understand, that you mean $c, n_0$ arbitrary? If yes, then you come to situation same with $(2)$.

Answer to Edit: Thanks for detail explanation. As far as I see it's ok. Let me say, that You start with assuming statement like my $(1)$, but to find contradiction in it you come to statement with type $(2)$: You created proof where $c$ is arbitrary non-negative and find $b$ (i.e. $a,n$) for it. And last note about this proof: You finish it with impossibility of $6\log{(a+3)} > (a+3)^2$, but how are you proving this last one? You will come to same efforts, as is needing to prove by limits, which I wrote in end of my answer. Sorry, for repeating one more time - obviously is possible not to use the word "limit", but essentially we are doing same.

And now about your aim to get $\log_{2}(n)=\Omega(\sqrt{n}) \Rightarrow n^2 = \Omega(2^n)$. I notice, that this implication is true only because first statement is false and answer to title is yes. So why we need it?

Let's come to main aim $\log_{2}(n) \neq \Omega(\sqrt{n})$. Formally, in same way with $(2)$, this is $$\forall c>0,\forall N\in\mathbb{N}, \exists n > N, \log_{2}(n) < c \cdot\sqrt{n}$$ So, we come to task for arbitrary $c$ search,find, appropriate $n$. I can, if you would like it, bring proof for $\frac{ \log_{2}(n)}{\sqrt{n}}< c$ "without limit" i.e. I'll not mention this word, by steps of inequalities, but essentially it will be same.

For Edit2:

I am left with the impression of a little more complexity than could have been avoided. When in conditions $\exists c \exists n_0 \forall n > n_0 $ you come to $\frac{4}{\ln{2} \cdot n^{1/4}} \geq c$ i.e. $n \leqslant \left(\frac{4}{\ln{2} \cdot c}\right)^4$, then this is already contradiction with Archimedean property of real numbers. Also, let me note, that Gary's inequality directly gives limit. For any $0<\alpha<1$ we can use inequality $$ \dfrac{log _{2}n}{n^{\alpha}} = \dfrac{1}{\alpha} \cdot \dfrac{log _{2}n^{\alpha}}{n^{\alpha}} \leqslant \dfrac{1}{\alpha} \cdot \dfrac{log _{2}(\lfloor n^{\alpha} \rfloor + 1)}{\lfloor n^{\alpha} \rfloor} = \dfrac{1}{\alpha} \cdot \dfrac{log _{2}\lfloor n^{\alpha} \rfloor }{\lfloor n^{\alpha} \rfloor} + \dfrac{1}{\alpha} \cdot \dfrac{1}{\lfloor n^{\alpha} \rfloor}$$ right side behaves as subsequence of $\dfrac{1}{\alpha} \cdot \dfrac{log _{2}n }{n} + \dfrac{1}{\alpha} \cdot \dfrac{1}{n}$

$\endgroup$
4
  • $\begingroup$ I've edited the question to show my full proof that $n^2 \neq \Omega(2^n)$. It is quite convoluted, sorry about that. It is definitely much easier to show using limits! However, my question was if I could use the fact that $n^2 \neq \Omega(2^n)$ to prove that $\log{n} \neq O(\sqrt{n})$. I believe that for $\log{n} = O(\sqrt{n})$ to be true, $n^2 = \Omega(2^n)$ would also have to be true. So I think I could say $a \to b$, $\neg b$, therefore $\neg a$. $\endgroup$ Commented Feb 11, 2022 at 2:58
  • $\begingroup$ As quick reply let me say, that if under comma we understand "and", then formally $$(a\Rightarrow b) \land (\neg b)= (\neg a \lor b)\land (\neg b) =\neg a \land (\neg b) $$ for last holds $\neg a \land (\neg b) \Rightarrow \neg a$. For new edition, let me time to read it and I'll come back to You. $\endgroup$
    – zkutch
    Commented Feb 11, 2022 at 3:19
  • $\begingroup$ I've edited the question with a proof for $\log{n} \neq \Omega(\sqrt{n})$. I used the inequality that Gary provided in a comment. Does my proof make sense? $\endgroup$ Commented Feb 11, 2022 at 20:51
  • $\begingroup$ Write answer to it also. $\endgroup$
    – zkutch
    Commented Feb 12, 2022 at 20:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .