Big-O definition question on the constant C

Question

Rosen's discrete Math textbook

From Rosen's discrete Math textbook. Based on the definition of Big-O given, do we assume C is positive or at least non-negative? Otherwise if not I feel the inequality wouldn't hold. Kindly let me know.

To further explain why I'm asking this question, look at this proof from the textbook explaining how if $f(x)$ is $O(x)$, then it's also $O(x^2)$:

The given information says that $|f(x)| \leq C|x|$ for all $x > k$, where $C$ and $k$ are particular constants. Let $k^{'}$ be the larger of $k$ and 1ドル$. Then since $|x| \leq |x^2|, \forall x > 1$, we have $|f(x)| \leq C|x^2|, \forall x > k^{'}$, as desired.

I feel this proof makes sense only when C is nonegative. Am I wrong though? Thoughts?

• Qiaochu Yuan: Yes, it should be non-negative. The point of this notation is to measure growth.
• EnEm: notice it says "if there are constants $C$" Ofcourse as you derived, these constants may only be positive, but that does not need to be included in the definition
• zkutch: In most of sources condition $C$ positive is placed in definition of big-O en.wikipedia.org/wiki/Big_O_notation
• John Douma: Since we are taking the absolute values of $f$ and $g,ドル it should be obvious that $C$ can't be negative.

Answer 1

The definition states that there is a constant $C$. Evaluating the inequality at any $x$ shows that $C\geqslant 0$. But the definition remains valid and does not need to the give condition on $C$!

Edit: there is one exception. If $f(x)=g(x)=0$ for all $x$, then $C$ can be any constant. In any case, you can always choose $C$ to be positive.

• Qiaochu Yuan: To be very pedantic, that's not true if $f = g = 0$.
• Kolakoski54: You're right, I was adding this point when you commented!
• Bob Marley: @Kolakoski54 Could you elaborate on "Evaluating the inequality at any x shows that C ⩾ 0" ?
• Kolakoski54: If $g$ is not always 0ドル,ドル let $x$ be such that $|g(x)|\ne 0$. Then $C\geqslant |f(x)/g(x)|\geqslant 0$.
• Bob Marley: @Kolakoski54 Hey I just added a further example to showcase context for my question. Kindly if you could check that too I'd be grateful.

Answer 2

The definition doesn't say the formula has to work for all choices of $C$.

In general, for any two functions $f(x)$ and $g(x)$ such that $f(x)$ is "big-O" of $g(x)$, there will be numerical values you can choose as the constant $C$ that will satisfy the inequality in the definition (provided that you also choose a suitable value of $k$); in most of those cases there are other numerical values you cannot use for $C$ because they simply don't allow the condition in the definition to be satisfied.

We don't care about the values of $C$ that don't work, and it's not necessary for the definition to specify what they are.

---

Proofs, however, are different from definitions, and knowing something about your constants can be useful.

The given information says that $|f(x)| \leq C|x|$ for all $x > k$, where $C$ and $k$ are particular constants. Let $k'$ be the larger of $k$ and 1ドル$. Then since $|x| \leq |x^2|, \forall x > 1$, we have $|f(x)| \leq C|x^2|, \forall x > k'$, as desired.

Technically, we do indeed need to know that $C \geq 0$ in order to make this proof work. If Rosen was very careful, he might have included some discussion between the definition and this proof to explain why we can assume there is not just any $C$, but actually a non-negative $C$, whenever we use the definition of big-O.

This claim can be proved from the definition, which is why it does not need to be stated as part of the definition. You can even go a little further and say something about $k$ as well.

Lemma. Let $f(x)$ be $O(g(x))$ and let $C_0$ and $k_0$ be any constants. Then there exist constants $C$ and $k$ such that $C > C_0$, $k > k_0$, and such that $|f(x)| \leq C|g(x)|$ whenever $x > k$.

Informally speaking, this lemma says that when applying the definition of big-O, you can assume the constants $C$ and $k$ are as great as you need them to be.

This makes it easier to prove that if $f(x)$ is $O(x)$ then $f(x)$ is $O(x^2)$, not just because we can insert the condition $C > 0$ in the statement of the definition of big-O, but also because we don't need $k'$; we can add the condition that $k > 1$.

I haven't given a proof of the lemma; I think it would be more useful to you to prove it yourself.

• Bob Marley: Hey I just added a further example to showcase context for my question. Kindly if you could check that too I'd be grateful.
• Bob Marley: Tysm for the lemma! As for proving it: Since $C > C_0$ we can multiply both sides of it by $|g(x)|$ to get $C|g(x)| \geq C_{0}|g(x)|,ドル which is true for all x in domain of g (correct? or am I wrong here?). Hence since we know that $f(x) \leq C_{0}|g(x)|$ at least whenever $x > k_0,ドル we know that $f(x) \leq C_{0}|g(x)| \leq C|g(x)|$ also whenever $x > k_0$. Since $k > k_0,ドル $x > k$ would be a subset of the set $x > k_0$ and hence mean the inequality is true for $x > k$ as well! Kindly let me know if my proof is correct
• Bob Marley: Also, just some few follow up questions regarding your answer:
• Bob Marley: 1. Why is it that "Technically, we do indeed need to know that C≥0 in order to make this proof work" (just want to make sure we're on the same page in our thinking here)?
• Bob Marley: 2. When you say "we can assume there is not just any C, but actually a non-negative C, whenever we use the definition of big-O." and how "this claim can be proved from the definition", could you kindly explain how it can be proven from the definition?

Answer 3

Let's do some casework:

1. $f = g = 0$: Then C can be any real number.
2. $|f| = 0$ and $|g| > 0$: Then 0ドル \leq C|g| \iff 0 \leq C$ (dividing both sides by $|g|$)
3. $|f| > 0$ and $|g| = 0$: Then C does not exist since $|f|$ can't be $> 0$ and $\leq 0$ at same time, hence contradiction.
4. $|f| > 0$ and $|g| > 0$: Then 0ドル < \frac{|f|}{|g|} \leq C$, hence C > 0.

Therefore C is for the most part going to be $\geq 0$ (with the exception of the 2 minor edge cases to consider). I'm not too sure if this is a valid argument. If anyone can check my proof I'd be grateful.

• Kolakoski54: I don't understand your conclusion "$C\leqslant 0$". Shouldn't it be the opposite?
• Bob Marley: @Kolakoski54 Yes sorry that's what I meant my bad.
• Bob Marley: @Kolakoski54 Also I'm not sure if my proof makes much sense since the values of f and g can vary and hence the absolute values of f and g (from =0 to >0)
• Kolakoski54: Well you better write, e.g., "there exist $x>k$ such that $|g(x)|>0$" rather than "$|g|>0$", and evaluate your condition at this $x$.