Question

Show that if \(f(x)\) is \(O(x)\), then \(f(x)\) is \(O({x^2})\).

Short answer

We have shown that \(f(x)\) is \(O(x)\), then \(f(x)\) is \(O({x^2})\).

Step-by-step solution

Step 1:

Using Big-O Notation definition, we can say that if \(f(x)\) is \(O(x)\) means that there exist constants \(C,k\) such that \(|f(x)| \le C|x|,\) whenever \(x > k\).

This means that \(f(x)\) is bounded on both sides, for sufficiently large value of \(x\).

Step 2:

If we assume that \(k > 1\), then we can say that,

\(\begin{array}{l}x > k\\ \Rightarrow x > 1\end{array}\)

Multiplying both sides by \(x\), we have

\(\begin{array}{l} \Rightarrow {x^2} > x\\ \Rightarrow x < {x^2}\end{array}\)

Step 3:

Multiplying both sides by \(C\) and take mod on both sides, we have

\( \Rightarrow C|x| < C|{x^2}|\).

Now, using \(|f(x)| \le C|x|,\) and \(C|x| < C|{x^2}|\), we can say that,

\(\begin{array}{l}|f(x)| \le C|x| < C|{x^2}|\\ \Rightarrow |f(x)| \le C|{x^2}|\end{array}\)

By definition of Big-O Notation, we can say that \(f(x)\) is \(O({x^2})\) for \(x > k > 1\).

We have shown that \(f(x)\) is \(O(x)\), then \(f(x)\) is \(O({x^2})\).