Prove that $n^2 + 2n + 3$ is $O(n^2)$. Find values for $C$ and $k$ that prove that they work.
Edit: In particular, I don't at all understand how to find C and k.
I asked a similar question but every response went way over my head. The similar question is linked here. Sorry, I guess I'm not that smart!
On
We have a polynomial $P(n)=n^2+2n+3$. Now, we want to find some constant $C$ and $k$ such that $P(n)\leq Cn^2$ for any $n\geq k$. We note that we can break the polynomial up in its different pieces, and if we make each piece $O(n^2)$, we would have made the whole polynomial $O(n^2)$. Let's start with the easy case: when is $$3\leq n^2$$ true? Well, $n=1$ fails, but $n=2$ doesn't, and we know $n^2$ will keep on growing. So we know $3$ is $O(n^2)$ with $C_1=1$, $k_1=2$. Now, look at $2n$. Then $n\leq n^2$ is true for any $n\geq 1$. So we find $2n$ is $O(n^2)$ with $C_2=2\times 1$ and $k_2=1$. Finally, $n^2$ is $O(n^2)$ since $n^2\leq n^2$ is always true, so $C_3=1$, $k_3=1$.
Finally, we take $C=C_1+C_2+C_3$ and $k_0=\max\{k_1,k_2,k_3\}$, and we are done: $P(n)$ is $O(n^2)$ with constant $C=1+2+1=4$ and $k=k_0=2$. I invite you to think about this last step.
On
We want to bound everything by a multiple of $n^2$. Notice that $$(3,2n,n^2)=(3,2,1), (3, 4, 4), (3, 6, 9), \cdots$$
You can see that $n^2$ bounds the other terms from above from the second term onwards, so you might as well take $n\ge 2$. If you prefer take $n\ge 100$ just to make sure.
Then the sum is at most $n^2 + n^2 + n^2$ from this point on, so $3n^2$ would do. Or $100n^2$ if you prefer.
I will try to give you a lengthy discussion of what $\mathcal O$ means. (All functions here are assumed non-negative, and their domains are the positive integers.)
You say $f = \mathcal O(g)$ if there exists $C > 0$ and $k > 0$ such that $Cg(n) > f(n)$ for all $n > k$.
Let's first investigate this definition when $C$ is not allowed to be chosen arbitrarily, but fixed at $1$.
$$ f = \mathcal O(g) \text{ if there exists } k > 0 \text{ such that } g(n) > f(n) \text{ for all } n > k. $$
This means that $g$ eventually dominates $f$.
For example, intuitively $n^2$ eventually dominates $2n$. (You can see this by plotting with Wolfram Alpha.) But you do have to prove formally that $n^2 > 2n$ actually holds when $n$ is big enough. By plugging in the first few test numbers, you can see that $3^2 > 2\cdot 3$, and $n^2$ continues to grow faster than $2n$ when $n > 2$. This gives you $k = 2$. Note, however, that you could also pick $k$ anything larger than $2$.
[I did skip one step when I claimed that $n^2$ continues to grow faster than $2n$ when $n > 2$. This can be proved by looking at the increment of each function as $n$ increases. Going from $n$ to $n + 1$, the first function increases by $(n+1)^2 - n^2 = 2n + 1$, while the second function increases by $2(n+1) - 2n = 2$. This means $n^2$ will grow faster than $2n$ when $2n + 1 > 2$, i.e., $n > \frac 12$. Since we pick $k = 2$, our claim above is valid.]
Next, we come to the discussion of $C$. The big O notation is intended to quantify the "degree of growth", so if we have a function, say $n^6$, we want to say that $n^6$, $2n^6$, $10n^6$ and so on all grow at the same degree. That is where $C$ comes into play.
Let me take the opportunity here to say that we could relax strict inequalities ($>$) in the definition of $\mathcal O$ to non-strict ones ($\ge$) without changing anything.
In the example you gave, $n^2 + 2n + 3$ is a sum of three terms: $n^2$, $2n$, and $3$. With the non-strict definition
Now you combine all these dominations into one by adding up $C$'s and taking the maximum of $k$'s. This can be written more formally as
For $n \ge 2$, \begin{align*} n^2 & \ge n^2 \\ n^2 & \ge 2n \\ n^2 & \ge 3 \\ \therefore 3n^2 & \ge n^2 + 2n + 3. \end{align*}
To conclude, the sentence $$ n \ge 2 \text{ implies } 3n^2 \ge n^2 + 2n + 3 $$ demonstrates $n^2 + 2n + 3 = \mathcal O(n^2)$ with $k = 2$ and $C = 3$.