In this example my textbook provides: $4n^2+21n+100$ is $O(n^2)$.
What I do not understand is that the book says the witnesses to this relationship is C = 8, K = 9. How did they come up with those number?
The book kind of gives an answer to how they came up with C = 8:
Suppose $n \ge 0$
$4n^2+21n+100 \le 4n^2+24n+100$ (Yes, the left is $21n$ and the right is $24n$)
$\le 4(n^2 + 6n + 25)$
$\le 8n^2$
I have no idea how they got these numbers, could someone explain this to me.
I also understand that if there is one pair of witnesses to a relationship, there exists an infinite number of witnesses therefore what is another pair that would be valid for this relationship? Thank you in advance!
The idea here is that they try to get some inequality of the form :
$$4n^2+21n+100 \leq Cn^2$$ to prove that this function is $O(n^2)$ .
The inequality they use :
$$4(n^2+6n+25) \leq 8n^2$$ is equivalent with : $$6n+25 \leq n^2$$ which is true for every $n \geq 9$ .
It doesn't matter which $C$ you choose as long as the inequality is true from some point on , for $n \geq n_0$ .
You could choose $C=1000$ to make things even simpler , as obviously :
$$4(n^2+6n+25) \leq 4(n^2+6n^2+25n^2)=128n^2 < 1000n^2$$ for every $n \geq 1$
You could also choose $n=4+ \epsilon$ for some very small $\epsilon$ and the inequality would be :
$$24n+100 \leq \epsilon n^2$$ which is true from some point on but for small numbers it fails .
They have thus chosen a bigger constant to make the inequality simpler to verify .