# 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.