How to prove that $n^2$ is not $o(n^2+10^{10}n)$? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-24T16:16:06Z https://cs.stackexchange.com/feeds/question/73815 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/73815 0 How to prove that $n^2$ is not $o(n^2+10^{10}n)$? Yos https://cs.stackexchange.com/users/70335 2017-04-11T17:57:41Z 2017-04-12T23:56:24Z <p>I need to prove that $n^2$ is not $o(n^2+10^{10}n)$. I thought of the limit test: $$\lim_{n \to \infty} \frac{n^2}{n^2+10^{10}n} = 1 \Rightarrow n^2 = \Theta(n^2+10^{10}n)$$</p> <p>However I'm not sure if the result of the test rules out the possibility of $o(n^2+10^{10}n)$.</p> https://cs.stackexchange.com/questions/73815/how-to-prove-that-n2-is-not-on21010n/73818#73818 6 Answer by David Richerby for How to prove that $n^2$ is not $o(n^2+10^{10}n)$? David Richerby https://cs.stackexchange.com/users/9550 2017-04-11T19:18:17Z 2017-04-11T19:18:17Z <p>One definition $f(n)=o(g(n))$ is that $\lim_{n\to\infty} f(n)/g(n)=0$. If this is the definition you're using, then showing that the limit is&nbsp;$1$ already shows that $f(n)\neq o(g(n))$.</p> <p>The other definition is that, for every $c&gt;0$, there is an $n_0$ such that $f(n)\leq cg(n)$ for all $n\geq n_0$. The fact that $\lim_{n\to\infty} f(n)/g(n)=1$ means that, for all $\varepsilon&gt;0$, there is some $n_0$ such that $f(n)/g(n)&gt;1-\varepsilon$ for all $n\geq n_0$ (this is part of the definition of "limit"). So, for all&nbsp;$\varepsilon&gt;0$, we have $f(n)&gt;(1-\varepsilon)g(n)$ for all large enough&nbsp;$n$. This means that, in particular, we do <em>not</em> have $f(n)\leq cg(n)$ for $c=1-\epsilon$, so $f(n)\neq o(g(n))$ by the alternative definition.</p> https://cs.stackexchange.com/questions/73815/how-to-prove-that-n2-is-not-on21010n/73870#73870 1 Answer by gnasher729 for How to prove that $n^2$ is not $o(n^2+10^{10}n)$? gnasher729 https://cs.stackexchange.com/users/17408 2017-04-12T20:27:49Z 2017-04-12T23:56:24Z <p>Without any limits: $(n^2 + 10^{10}n) / 2 ≤ n^2 ≤ n^2 + 10^{10}n$ whenever $n ≥ 10^{10}$. So for c &lt; 1/2, we don't have $n^2 &lt; c(n^2 + 10^{10}n)$ for all large n. Actually, not for any large n. </p> <p>And $f(n) = \Theta (g(n))$ does indeed rule out that $f(n) = o (g(n))$, but is not a necessary condition. </p>