# Proof that $O(n^2 + n + a)$ is a subset of $O(n^2)$

I'm new to the Big-O Notation and couldn't find any question that covers my problem of understanding. From my intuition, it is clear that for $n\rightarrow+\infty$, that $n^2+n+a$ "behaves" like $n^2$, so any function that has an upper bound in the form of $n^2+n+a$ also has an upper bound of the form $n^2$, but the $n_0$ and $c$ will be different.

Unfortunately, I fail to proof formally that this is correct. If somebody could provide a proof using the Big-O definition, I would be glad.

• Step 1: write down the definition of Big-O notation – Christopher May 31 '18 at 9:53

## 1 Answer

Let $f(n) \in \mathcal O(n^2 +n+a)$ with $$f(n) \le c_0 (n^2 +n+a)\quad\forall n\ge n_0$$

Now chose $n_1 = \max(a, 2, n_0)$ such that $n_1^2 \ge n_1 +a$. Then $$f(n) \le c_0 (n^2 + n + a) = c_0 n^2 + c_0 (n+a) \le c_0 n^2 + c_0 n^2 = 2c_0 n^2 \quad\forall n \ge n_1$$ Thus $f(n) \in \mathcal O(n^2)$ for constants $n_1$ and $c_1 := 2c_0$.

More generally you can prove that $f\in\mathcal O(g)$ and $g\in \mathcal O(h)$ implies $f\in\mathcal O(h)$ as well as $\mathcal O(g) = \mathcal O(f + g)$.

• Thanks a lot! I wasn't able to find a $n_1$, but your choice makes sense. – Maxbit May 31 '18 at 11:30
• @Maxbit That is essentially the choice for proving $n+a\in\mathcal O(n^2)$ and then using the more general statement. – AlexR May 31 '18 at 11:54
• Sorry, I have to ask one more thing: It is clear to me that $n_{1}^2 \ge n_1 + a$. But I'm not really sure about why $n_1 = max(2a, 2, n_0)$. Isn't $n_{1}^2 \ge n_1 + a$ sufficient? Why did you chose the 3 values and why are they necessary? – Maxbit May 31 '18 at 13:29
• You also need $n_1 \ge n_0$ for the first inequality. – AlexR May 31 '18 at 13:30
• Okay, then we need to chose an $n_1$ such that $n_{1}^2 \ge n_1 + a$ and $n_1 \ge n_0$, but unfortunately I don't see how to get from that to $n_1 = max(2a, 2, n_0)$. – Maxbit May 31 '18 at 13:32