0
$\begingroup$

I have to solve the following $n^2+n \in O(n^2−n)$.

I did it this way: $n^2+n \in O(n^2−n) = n^2 \in O(n^2−n) = n^2 / n^2-n = 2n / 2n-n$ which is infinite.

I don't know if this is correct because the $-n$ in the $O$ notation is confusing me and I haven't found anything about it online. I know if this would be at example -1000 that $n^2+n \in O(n^2−n)$ would be correct.

Could someone explain it to me ?

$\endgroup$
  • $\begingroup$ Duplicate of our reference question. $\endgroup$ – Raphael May 15 '17 at 5:21
  • $\begingroup$ "I haven't found anything about it online" -- You need to work on your searching skills. Given the definition of $O$, it's clear that the $-n$ is irrelevant, so you'll not find anything if you search for "minus in big-oh" or something like that. $\endgroup$ – Raphael May 15 '17 at 5:22
4
$\begingroup$

$f \in O(g)$ means there's $n_0$ and $c>0$ such that $n>n_0$ implies $f(n) \leq cg(n)$.

Note that for $n>2$, we have $n^2 \geq 3n$.

Then, for $n>2$, we have: $$ \begin{align} 2(n^2 - n) & = n^2 - 2n + n^2 \\ & \geq n^2 - 2n + 3n\\ & = n^2 + n\\ \end{align} $$

Summarizing: for $n>2$, we have $n^2+n \leq 2(n^2-n)$. Thus $n^2+n \in O(n^2-n)$.

$\endgroup$
  • $\begingroup$ Where do you get the 3n from ? $\endgroup$ – Mattjo May 2 '17 at 16:45
  • $\begingroup$ If you follow the line "Then...", then you see that n^2 >= 3n is exactly the term needed to make the inequalities work. Working backwards from there, one gets the lower limit for n: n>=3 or equivalently n>2. $\endgroup$ – Paul Hankin May 2 '17 at 17:01
  • $\begingroup$ I understand. Thank you very much for the quick answers ! $\endgroup$ – Mattjo May 2 '17 at 17:07

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.