3
$\begingroup$

Show that the function, $T(n) = 4n^2$ is NOT $O(n)$.

I'm not looking for someone to give me a full answer, I just need some pointers on how to go about starting to show that it is not $O(n)$.

Many thanks in advance.

$\endgroup$
  • 2
    $\begingroup$ Assume it is. Write down what this would mean. Obtain a contradiction. $\endgroup$ – David Mitra Feb 5 '14 at 21:33
  • 2
    $\begingroup$ What is 4n2? $4n^2$? $\endgroup$ – Hagen von Eitzen Feb 5 '14 at 21:34
  • 1
    $\begingroup$ Explore the fraction $\frac{4n^2}{n}$ (I am assuming $n$ is a natural number). If you assume the claim is true, there must be some number, call it $N$, and some other value, call it $M$, such that $\frac{4n^2}{n} < M$ whenever you pick any number $n > N$. This won't be the case here after you reduce the fraction in question. Why not? $\endgroup$ – Darrin Feb 5 '14 at 21:39
5
$\begingroup$

Use proof by contradiction: Assume that $4n^2=O(n)~~\forall n\geq 1$, then constant $c$ exist $c<\infty$ such that $4n^2\leq cn$, therefore $n\leq \frac{c}{4}$, since the inequality should hold for all $n$'s, and it doesn't hold for $n=\frac{c}{4}+1$, then there is a contradiction in the initial assumption. Therefore $4n^2\neq O(n)$

$\endgroup$
  • 2
    $\begingroup$ Quote: "I'm not looking for someone to give me a full answer, I just need some pointers on how to go about starting..." $\endgroup$ – Did Feb 5 '14 at 22:01
3
$\begingroup$

Naively $O(n)$ represents functions $f(n)$ such that $\lim_{n\to\infty}|\frac{f(n)}{n}|<\infty$. Since $T(n)=4n^2$,$\lim_{n\to\infty}|\frac{4n^2}{n}|=\lim_{n\to\infty}|4n|=\infty$. So $T(n)$ is not $O(n)$.

$\endgroup$
  • $\begingroup$ In my opinion this is the best answer as it uses the idea behind big O directly. It is also concise. $\endgroup$ – TooTone Feb 5 '14 at 23:26
  • $\begingroup$ @TooTone I think that the edit changes the content significantly: $O(n)$ is not the same as $f(n)/n$ having finite limit, but rather that $f(n) / n$ remains bounded as $n$ grows (hence the use of the word "naively" in the original answer). $\endgroup$ – user61527 Feb 5 '14 at 23:46
  • $\begingroup$ @T.Bongers thankyou for pointing this out. It seems that I have screwed this one up royally, with the best of intentions: I just wanted to make what I thought was the best answer even better. I will let you or the answerer edit it back. $\endgroup$ – TooTone Feb 5 '14 at 23:49
  • $\begingroup$ @TooTone Not a problem; I'll just roll back the edit to the original answer. $\endgroup$ – user61527 Feb 5 '14 at 23:50
2
$\begingroup$

Assuming that $4n2$ means $4n^2$. Recall that something being $O(n)$ means that its absolute avlue is less than $Cn$ for some fixed constant $C$ and for all $n$ (possibly only sufficiently large, depending on your convention) $n$, where $n$ are presumably positive integers.

Now, think about if the inequality $4n^2 \le C n$ can possibly hold for all (sufficiently large) $n$ with one and the same fixed $C$.

$\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.