-2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Here $C$ and $k$ are constants, while $x$ is not. $\endgroup$ – Pontus May 4 '17 at 20:36
  • 1
    $\begingroup$ 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! $\endgroup$ – Raphael May 5 '17 at 5:19
  • 1
    $\begingroup$ You need to check the definition of $O$. You can also check out our reference questions. $\endgroup$ – Raphael May 5 '17 at 5:20
  • 2
    $\begingroup$ I've transcribed the image but please tell us the source of the quote. What textbook did it come from? $\endgroup$ – David Richerby May 5 '17 at 9:35
1
$\begingroup$

It is supposed there exists constant C and constant k such that the inequality holds. Constant C doesnt depend on x. Thus if x is greater than 7*C the inequality doesnt hold.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.