4

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.

yoknapatawpha
  • 4,009
Steven H
  • 49
  • 2
    Assume it is. Write down what this would mean. Obtain a contradiction. – David Mitra Feb 05 '14 at 21:33
  • 2
    What is 4n2? $4n^2$? – Hagen von Eitzen Feb 05 '14 at 21:34
  • 1
    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? – Darrin Feb 05 '14 at 21:39

3 Answers3

6

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)$

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

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

Spock
  • 1,663
  • 2
  • 13
  • 26
  • In my opinion this is the best answer as it uses the idea behind big O directly. It is also concise. – TooTone Feb 05 '14 at 23:26
  • @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). –  Feb 05 '14 at 23:46
  • @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. – TooTone Feb 05 '14 at 23:49
  • @TooTone Not a problem; I'll just roll back the edit to the original answer. –  Feb 05 '14 at 23:50
2

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

quid
  • 42,135