# Understanding constants in big-O notation

I am having a difficult time understanding big-O notation for the growth of functions. My textbook says the following.

Example 2 shows that $7x^2$ is $O(x^3)$. Is it also true that $x^3$ is $O(7x^2)$?

Solution: To detemine whether $x^3$ is $O(7x^2)$, we need to determine whether witnesses $C$ and $k$ exist, so that $x^3\leq C(7x^2)$ whenever $x>k$. We will show that no such witnesses exist using a proof by contradiction.

If $C$ and $k$ are witnesses, the inequality $x^3\leq C(7x^2)$ holds for all $x>k$. Observe that the inequality $x^3\leq C(7x^2)$ is equivalent to the inequality $x\leq 7C$, which follows by dividing both sides by the positive quantity $x^2$. However, no matter what $C$ is, it is not the case that $x\leq 7C$ for all $x>k$, no matter what $k$ is, because $x$ can be made arbitrarily large. It follows that no witnesses $C$ and $k$ exist for this proposed big-$O$ relationship. Hence, $x^3$ is not $O(7x^2)$. $\quad\Box$

I don't understand the part that says, ".... no matter what $C$ is because $x$ can be arbitrary large." Making $x$ large, can't we also assign larger number for $C$?

What are the purpose of $C$ and $k$?

Are there any rules regarding assigning values to them?

• Here $C$ and $k$ are constants, while $x$ is not. – Pontus May 4 '17 at 20:36
• Welcome to Computer Science! Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! – Raphael May 5 '17 at 5:19
• You need to check the definition of $O$. You can also check out our reference questions. – Raphael May 5 '17 at 5:20
• I've transcribed the image but please tell us the source of the quote. What textbook did it come from? – David Richerby May 5 '17 at 9:35

To prove that a function $f(n)$ is in $O(g(n))$ we must find two constants $c$ and $k$ so that $0 \leq f(n) \leq cg(n)$ for all $n > k$.
An example of this applied towards a function could be $f(n) = 7n^2$. We can prove this function is in $O(n^2)$ by selecting $c = 8$ and $k = 2$. Then, through substitution we can see that $0 \leq 7n^2 \leq 8n^2$ whenever $n > 2$ (of course, we could select other $c$'s or $k$'s, but we only need to find one set).
To prove that $f(n) = n^3$ is not in $O(7n^2)$, we must demonstrate that there is no possible combination of $c$ and $k$ for the inequality $0 \leq n^3 \leq c * 7n^2$ to hold for all $n > k$.
Suppose there is a combination to fulfill the inequality, we will call these numbers $c_0$ and $k_0$. If $f(n) \in O(7n^2)$, we know that $0 \leq n^3 \leq c_0 * 7n^2$. Working with the inequality, we can see that $n$ should be less than or equal to $c_0 * 7$ for all $n > k_0$, but we can select $n = \text{max}(\{k_0 + 1, c_0 * 7 + 1\})$ and the inequality wouldn't hold.