0
$\begingroup$

DEFINITION: $f = O(g)$ if positive integers c and $n_0$ exist such that for every integer $n$ $\geq$ $n_0$, $f(n) ≤ c·g(n)$

so:

$n^2 \leq c·log(n)$

$\frac{n^2}{log(n)} \leq c$

is this enough proof? since the fraction will grow larger and larger depending on n>1, so its false?

$\endgroup$
4
$\begingroup$

This is not "enough proof". The main problem of your proof is that it just lacks words. A proof should explain what you have in your head. So the first thing is to clearly states what you want to prove.

We want to prove that $n^2$ is not $O(\log n)$.

Then you have to explain how you will do it:

Assume toward a contradiction that $n^2=O(\log(n))$.

So you are going to do derive a contradiction from this assumption. We just apply definitions.

By definition, it means that there exists $c, n_0$ such that for every $n \geq n_0$, $n^2 < c \log n$, that is, ${n^2 \over \log n} < c$.

Now you need to explain why this is absurd. There are many ways of doing it depending on what you assume the reader to be familiar with. One way to go is the following:

It is well known that $\lim_{n \rightarrow \infty}{n^2 \over \log n} = \infty$. Thus, there exists $n_1 \geq n_0$ such that ${n_1^2 \over \log n_1} \geq c$, contradicting the initial assumption.

Now, you conclude:

Thus, $n^2$ is not $O(\log n)$.

If you think your reader is not familiar enough with limits you can then go more into details:

We know that for every $n \in \mathbb{N}$, $\log(n) \leq n$. Tus, $n = {n^2 \over n} \leq {n^2 \over \log n}$. Thus, $n_1 = \max(n_0,c)$ verifies both $n_1 \geq n_0$ and $c \leq n_1 \leq {n_1^2 \over \log n_1}$ which contradicts the intial hypothesis.

$\endgroup$
3
$\begingroup$

There is no constant $c$ such that $c \geq \frac{n^2}{\log {n}}$ for every $n\geq n_0$. Hence, $n^2 \notin O(\log n)$

$\endgroup$
  • $\begingroup$ This clears nothing up since it only restates the what the OP already claims in the question. There is still no proof that the fraction is unbounded. Which isn't hard, but apparently not trivial (or else the OP wouldn't have to ask the question). (Also, note that you have to prove that no $n_0$ works, too.) $\endgroup$ – Raphael Feb 20 '18 at 7:49

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.