Discrete Math

Suppose \(f\) and \(g\) are real valued functions from \(f(x):\mathbb{R}→\mathbb{R}\), we say \(f(x)\) is Big \(O\) of \(g(x)\), written \(f(x)\) is \(O(g(x))\), if there exists positive integers \(A\) and \(n\), so that \(|f(x)| \leq A|g(x)|\) whenever \(x > n\).

Show that \(f\left(x\right)=2x^2 +4x\) is \(O(x^2)\)

While intuitively we may understand that the dominant term for large \(x\) is \(x^2\) so that \(f(x) = O\left(x^2\right)\), we show this formally by producing as witnesses \(A=3\) and \(n =4\) with reference to the following graph.

Show that \(f(x) =2x^3 +3x\) is \(O(x^3)\), with \(A=3\) and \(n=2\). Support your answer graphically.

Notice that \( x^3 > 3x\) when \( x \geq 2\). This means \(2x^3 +x^3 > 2x^3 +3x \) when \(x >2 \). In other words \( 3x^3 > 2x^3 +3x\) whenever \( x>2\), confirming \(A=3\) and \(n=2\) as witnesses, and supported by the following graph.

Show that \( f(x) = x^2\) is not \( O( \sqrt{x})\).

Consider the graphs of \( \sqrt{x}\), \( 2 \sqrt{x}\), \( 3\sqrt{x}\), and the graph of \(x^2\). Notice that eventually, or for \(x\) large enough, \(x^2\) is larger than any \(A \sqrt{x}\) as in the figure below

Suppose \(A>1\) is given and fixed , then if \( f(x) = x^2\) is \( O(g(x))=O( \sqrt{x})\) , there is a corresponding \(n\), also fixed , for which \(A \sqrt{x} \geq x^2\) whenever \(x>n\).

We solve the inequality \(A \sqrt{x} ≥ x^2\) by dividing both sides by \(\sqrt{x} =x^{1/2}\), to obtain, \(A \sqrt{x} ≥ x^{3/2}\).

But \(A\) is fixed and cannot be greater than all arbitrarily large \( x^{3/2}\). Hence no such \(n\) can exist for a given fixed \(A\).

For example, consider \(g(x)=A \sqrt{x}\) and \( f(x) =x^2 \), when \( x= A^2\) we obtain \( g(A^2) = A \sqrt{(A^2)}= A^2\) and \( f(A^2) = {\left ( {A}^2 \right )}^2\) and \( f(A^2)= A^4 > A^2 = g(A^2) \) when \(A>1\).

\(p(x)=a_nx^n +a_{n-1}x^{n-1} +a_{n-2}x^{n-2}+\ldots +a_2x^2 +a_1x^1+a_0\) is \(O(x^n)\)

Order the following functions by growth: \(n⋅\log_2⁡ n\) , \(n^2\), \(n^{4/3}\)

Recall the ordering,

\(\log_2⁡ n\), \(n^{1/3}\), and \(n\),

which is ordered by logarithmic, then radical, and then polynomial (or linear) growth.

Notice also, that multiplying each by \(n\), preserves the order.

\(n⋅\log_{2⁡}n=n\times \log_{2⁡}n\)

\(n^{4/3} =n \times n^{1/3}\)

\(n^2=n \times n\)

The using the original ordering, \(\log{n}\), \(n^{1/3}\), \(n\), we obtain also the following ordering \(n⋅\log n\), \(n^{4/3}\), \(n^2\).

Find the Big O of each of the following and then rank by Big \(O\) growth:

\(f\left(x\right)=\left({3x}^3+x\right)2^x+\left(x+x!\right)x^4\)

\(g\left(x\right)=x^x(2^x+x^2)\)

\(h\left(x\right)=5x!+4x^3\log{x}\)

First consider \(f\left(x\right)\) and using the polynomial property observe that \(\left({3x}^3+x\right)\) is \(O(x^3)\). Using the multiplicative property, conclude that \(\left({3x}^3+x\right)2^x\) is \(O(x^32^x)\). Likewise using the sum property, \(\left(x+x!\right)\) is \(O\left(\max{\left(x,x!\right)}\right)= O (x!)\). Then using the multiplicative property, \(\left(x+x!\right)x^4\) is \(O (x^4x!)\). Then \(f\left(x\right)=\left({3x}^3+x\right)2^x+\left(x+x!\right)x^4\) is \(O\left(\max{\left(x^32^x,x^4x!\right)}\right)=O\left(x^4x!\right)\).

For \(g(x)\), notice using the maximum property for the sum, that \(2^x+x^2\) is \(O(2^x)\). Then using the multiplicative property, \(x^x(2^x+x^2)\) is \(O(2^xx^x)\).

For \(h\left(x\right)\), we want \(O\left(\max{\left(x!,\ x^3\log{x}\right)}\right)=O(x!)\). Notice here, that \(4x^3\log{x}\) is \(O(x^4)\), and \(x^4\) has smaller asymptotic growth than \(x!\). In fact, \(x^4\) is \(O(x!)\).

So, \(f(x)\) is \(O\left(x^4x!\right)\), and \(g(x)\) is \(O\left(2^xx^x\right)\). Also, \(h(x)\) is, \(O\left(x!\right)\).

We conclude that from an ordering perspective, we have by increasing growth order, \(h(x)\), \(f(x)\), and \(g(x)\). To convince yourself that \(g(x)\) grows faster than \(f(x)\), use the facts that \(2^x\) grows faster than \(x^4\), and \(x^x\) grows faster than \(x!\).