0
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Thanks a lot! I wasn't able to find a $n_1$, but your choice makes sense. $\endgroup$ – Maxbit May 31 '18 at 11:30
  • $\begingroup$ @Maxbit That is essentially the choice for proving $n+a\in\mathcal O(n^2)$ and then using the more general statement. $\endgroup$ – AlexR May 31 '18 at 11:54
  • $\begingroup$ 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? $\endgroup$ – Maxbit May 31 '18 at 13:29
  • $\begingroup$ You also need $n_1 \ge n_0$ for the first inequality. $\endgroup$ – AlexR May 31 '18 at 13:30
  • $\begingroup$ 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)$. $\endgroup$ – Maxbit May 31 '18 at 13:32

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.