Question

Show that each of these pairs of functions are of the same order.

\(\begin{aligned}{l}a){\rm{ }}3x + 7,x{\rm{ }}\\b){\rm{ }}2{x^2} + x - 7,{\rm{ }}{x^2}{\rm{ }}\\c)\left( {x + 1/2} \right),x{\rm{ }}\\d){\rm{ }}log\left( {{x^2} + {\rm{ }}1} \right),{\rm{ }}lo{g_2}{\rm{ }}x{\rm{ }}\\e){\rm{ }}lo{g_{10}}{\rm{ }}x,{\rm{ }}lo{g_2}{\rm{ }}x\end{aligned}\)

Short answer

a. \(f(x) = 3x + 7\) and \(g\left( x \right) = x\) have the same order.

b. \(f(x) = 2{x^2} + x - 7\) and \(g\left( x \right) = {x^2}\) have the same order.

c. \(f(x) = \left( {x + \frac{1}{2}} \right)\) and \(g\left( x \right) = x\) have the same order.

d. \(f(x) = log\left( {{x^2} + {\rm{ }}1} \right)\) and \(g\left( x \right) = lo{g_2}{\rm{ }}x{\rm{ }}\) have the same order.

e. \(f(x) = lo{g_{10}}{\rm{ }}x\) and \(g\left( x \right) = lo{g_2}{\rm{ }}x\) have the same order.

Step-by-step solution

Write the definitions.

Big-O Notation:Let the real or complex values function is\(f\)and real valued function is\(g\). Then\(f\left( x \right)\)is\(O\left( {g\left( x \right)} \right)\). When there exists a positive real number\(M\)and real number\(k\)such that\(\left| {\left. {f\left( x \right)} \right|} \right. \ge M\left| {\left. {g\left( x \right)} \right|} \right.\forall x > k,\)where\(M\)and\(k\)are not unique.

Big-Omega Notation:Let the real or complex values function is\(f\)and real valued function is\(g\). Then\(f\left( x \right)\)is\(\Omega \left( {g\left( x \right)} \right)\). When there exists a positive real number\(M\)and real number\(k\)such that\(\left| {\left. {f\left( x \right)} \right|} \right. \ge M\left| {\left. {g\left( x \right)} \right|} \right.\forall x > k,\)where\(M\)and\(k\)are not unique.

Big-Theta Notation: If \(f\left( x \right)\) is \(O\left( {g\left( x \right)} \right)\) and \(f\left( x \right)\) is \(\Omega \left( {g\left( x \right)} \right)\), then \(f\left( x \right)\) is \(\Theta \left( {g\left( x \right)} \right)\). So, we can conclude that \(f\) has the same order as \(g\).

Show that \(f(x) = 3x + 7\) and \(g\left( x \right) = x\) have the same order.

Part-(a)

Using Big-O notation:

Let us take\(k = 7\), so we have\(x > 7\)

\(\begin{aligned}{l}\left| {\left. {f\left( x \right)} \right|} \right. = \left| {\left. {3x + 7} \right|} \right.\\{\rm{ }} = 3x + 7\\{\rm{ }} > 3x + x\\{\rm{ }} = 4\left| {\left. x \right|} \right.\end{aligned}\)

So, by definition of Big-O notation we have, \(f(x) = 3x + 7\)is \(O\left( x \right)\) having \(k = 7\) and \(M = 4\).

Using Big-Omega notation:

Let us take\(k = 0\), so we have\(x > 0\)

\(\begin{aligned}{l}\left| {\left. {f\left( x \right)} \right|} \right. = \left| {\left. {3x + 7} \right|} \right.\\{\rm{ }} = 3x + 7\\{\rm{ }} > 3x\\{\rm{ }} = 3\left| {\left. x \right|} \right.\end{aligned}\)

So, by definition of Big-Omega notation we have, \(f(x) = 3x + 7\)is \(\Omega \left( x \right)\) having \(k = 0\) and \(M = 3\).

Since \(f(x) = 3x + 7\)is \(O\left( x \right)\) and \(f(x) = 3x + 7\)is \(\Omega \left( x \right)\), so we have \(f(x) = 3x + 7\)is \(\Theta \left( x \right)\) and,

Therefore, \(f(x) = 3x + 7\) and \(g\left( x \right) = x\) have the same order.

Show that \(f(x) = 2{x^2} + x - 7\) and \(g\left( x \right) = {x^2}\) have the same order.

Part-(b)

Using Big-O notation:

Let us take\(k = 2\), so we have\(x > 2\)

\(\begin{aligned}{l}\left| {\left. {f\left( x \right)} \right|} \right. = \left| {\left. {2{x^2} + x - 7} \right|} \right.\\{\rm{ }} = 2{x^2} + x - 7\\{\rm{ < }}2{x^2} + x\\{\rm{ = }}2{x^2} + {x^2}\end{aligned}\)

\(\begin{aligned}{l}{\rm{ = }}3{x^2}{\rm{ }}\\{\rm{ = }}3\left| {\left. {{x^2}} \right|} \right.\end{aligned}\)

So, by definition of Big-O notation we have, \(f(x) = 2{x^2} + x - 7\) is \(O\left( {{x^2}} \right)\) having \(k = 2\) and \(M = 3\).

Using Big-Omega notation:

Let us take\(k = 3\), so we have\(x > 3\)

\(\begin{aligned}{l}\left| {\left. {f\left( x \right)} \right|} \right. = \left| {\left. {2{x^2} + x - 7} \right|} \right.\\{\rm{ }} = 2{x^2} + x - 7\\{\rm{ > }}2{x^2} - 7\\{\rm{ > }}\left| {\left. {{x^2}} \right|} \right.\end{aligned}\)

So, by definition of Big-Omega notation we have, \(f(x) = 2{x^2} + x - 7\) is \(\Omega \left( {{x^2}} \right)\) having \(k = 3\) and \(M = 1\).

Since \(f(x) = 2{x^2} + x - 7\)is \(O\left( {{x^2}} \right)\) and\(f(x) = 2{x^2} + x - 7\) is \(\Omega \left( {{x^2}} \right)\), so we have \(f(x) = 2{x^2} + x - 7\)is \(\Theta \left( {{x^2}} \right)\) and,

Therefore, \(f(x) = 2{x^2} + x - 7\) and \(g\left( x \right) = {x^2}\) have the same order.

Show that \(f(x) = \left( {x + \frac{1}{2}} \right)\) and \(g\left( x \right) = x\) have the same order.

Part-(c)

Using Big-Omega notation:

Let us take\(k = 1\), so we have\(x > 1\)

\(\begin{aligned}{l}\left| {\left. {f\left( x \right)} \right|} \right. = \left| {\left. {\left( {x + \frac{1}{2}} \right)} \right|} \right.\\{\rm{ }} = x + {\raise0.7ex\hbox{$1$} \!\mathord{\left/

{\vphantom {1 2}}\right.\kern-\nulldelimiterspace}

\!\lower0.7ex\hbox{$2$}}\\{\rm{ }} > x\\{\rm{ }} = \left| {\left. x \right|} \right.\end{aligned}\)

So, by definition of Big-O notation we have, \(f(x) = \left( {x + \frac{1}{2}} \right)\) is \(\Omega \left( x \right)\) having \(k = 1\) and \(M = 1\).

Using Big-O notation:

Let us take\(k = 1\), so we have\(x > 1\)

\(\begin{aligned}{l}\left| {\left. {f\left( x \right)} \right|} \right. = \left| {\left. {\left( {x + \frac{1}{2}} \right)} \right|} \right.\\{\rm{ }} = \left( {x + \frac{1}{2}} \right)\\{\rm{ < }}x + \frac{1}{2}\\{\rm{ < }}x + x\end{aligned}\)

\(\begin{aligned}{l}{\rm{ = 2}}x{\rm{ }}\\{\rm{ = 2}}\left| {\left. x \right|} \right.\end{aligned}\)

So, by definition of Big-O notation we have, \(f(x) = \left( {x + \frac{1}{2}} \right)\) is \(O\left( x \right)\) having \(k = 1\) and \(M = 2\).

Since \(f(x) = \left( {x + \frac{1}{2}} \right)\) is \(O\left( x \right)\) and\(f(x) = \left( {x + \frac{1}{2}} \right)\) is \(\Omega \left( x \right)\), so we have \(f(x) = \left( {x + \frac{1}{2}} \right)\)is \(\Theta \left( x \right)\) and,

Therefore, \(f(x) = \left( {x + \frac{1}{2}} \right)\) and \(g\left( x \right) = x\) have the same order.

Show that \(f(x) = log\left( {{x^2} + {\rm{ }}1} \right)\) and \(g\left( x \right) = lo{g_2}{\rm{ }}x\) have the same order.

Part-(d)

Using Big-O notation:

Let us take\(k = 2\), so we have\(x > 2\)

\(\begin{aligned}{l}\left| {\left. {f\left( x \right)} \right|} \right. = \left| {\left. {log\left( {{x^2} + {\rm{ }}1} \right)} \right|} \right.\\{\rm{ }} = log\left( {{x^2} + {\rm{ }}1} \right)\\{\rm{ < }}lo{g_2}\left( {{x^2} + {\rm{ }}1} \right)\\{\rm{ < }}lo{g_2}\left( {{x^2} + {\rm{ }}{x^2}} \right)\end{aligned}\)

\(\begin{aligned}{l}{\rm{ = }}lo{g_2}\left( {2{x^2}} \right){\rm{ }}\\ < lo{g_2}\left( {4{x^2}} \right)\\ = lo{g_2}\left( {{{\left( {2x} \right)}^2}} \right)\\ = 2lo{g_2}\left( {2x} \right)\end{aligned}\)

\(\begin{aligned}{l} < 2lo{g_2}\left( {{x^2}} \right)\\ = 4lo{g_2}x\\ = 4\left| {\left. {lo{g_2}} \right|} \right.\end{aligned}\)

So, by definition of Big-O notation we have, \(f(x) = log\left( {{x^2} + {\rm{ }}1} \right)\) is \(O\left( {lo{g_2}{\rm{ }}x{\rm{ }}} \right)\) having \(k = 2\) and \(M = 4\).

Using Big-Omega notation:

Let us take\(k = 1\), so we have\(x > 1\)

\(\begin{aligned}{l}\left| {\left. {f\left( x \right)} \right|} \right. = \left| {\left. {log\left( {{x^2} + {\rm{ }}1} \right)} \right|} \right.\\{\rm{ }} = log\left( {{x^2} + {\rm{ }}1} \right)\\{\rm{ = }}\frac{{lo{g_2}\left( {{x^2} + {\rm{ }}1} \right)}}{{lo{g_2}\left( {10} \right)}}\\{\rm{ > }}\frac{{lo{g_2}\left( x \right)}}{{lo{g_2}\left( {10} \right)}}\end{aligned}\)

\( = \frac{1}{{lo{g_2}\left( {10} \right)}}\left| {\left. {lo{g_2}\left( x \right)} \right|} \right.\)

So, by definition of Big-Omega notation we have, \(f(x) = log\left( {{x^2} + {\rm{ }}1} \right)\) is \(\Omega \left( {lo{g_2}{\rm{ }}x{\rm{ }}} \right)\) having \(k = 1\) and \(M = = \frac{1}{{lo{g_2}\left( {10} \right)}}\).

Since \(f(x) = log\left( {{x^2} + {\rm{ }}1} \right)\) is \(O\left( {lo{g_2}{\rm{ }}x{\rm{ }}} \right)\) and\(f(x) = log\left( {{x^2} + {\rm{ }}1} \right)\) is \(\Omega \left( {lo{g_2}{\rm{ }}x{\rm{ }}} \right)\), so we have \(f(x) = log\left( {{x^2} + {\rm{ }}1} \right)\)is \(\Theta \left( {lo{g_2}{\rm{ }}x{\rm{ }}} \right)\) and,

Therefore, \(f(x) = log\left( {{x^2} + {\rm{ }}1} \right)\) and \(g\left( x \right) = lo{g_2}{\rm{ }}x{\rm{ }}\) have the same order.

Show that \(f(x) = lo{g_{10}}{\rm{ }}x\) and \(g\left( x \right) = lo{g_2}{\rm{ }}x\) have the same order.

Part-(e)

Using Big-O notation:

Let us take\(k = 1\), so we have\(x > 1\)

\(\begin{aligned}{l}\left| {\left. {f\left( x \right)} \right|} \right. = \left| {\left. {lo{g_{10}}{\rm{ }}x} \right|} \right.\\{\rm{ }} = lo{g_{10}}{\rm{ }}x\\{\rm{ < }}lo{g_2}{\rm{ }}x\\{\rm{ < }}\left| {\left. {lo{g_2}{\rm{ }}x} \right|} \right.\end{aligned}\)

So, by definition of Big-O notation we have, \(f(x) = lo{g_{10}}{\rm{ }}x\) is \(O\left( {lo{g_2}{\rm{ }}x{\rm{ }}} \right)\) having \(k = 1\) and \(M = 1\).

Using Big-Omega notation:

Let us take\(k = 1\), so we have\(x > 1\)

\(\begin{aligned}{l}\left| {\left. {f\left( x \right)} \right|} \right. = \left| {\left. {lo{g_{10}}{\rm{ }}x} \right|} \right.\\{\rm{ }} = lo{g_{10}}{\rm{ }}x\\{\rm{ = }}\frac{{lo{g_2}\left( x \right)}}{{lo{g_{10}}\left( {10} \right)}}\\{\rm{ = }}\frac{1}{{lo{g_{10}}\left( {10} \right)}}\left| {\left. {lo{g_2}{\rm{ }}x} \right|} \right.\end{aligned}\)

So, by definition of Big-O notation we have, \(f(x) = lo{g_{10}}{\rm{ }}x\) is \(\Omega \left( {lo{g_2}{\rm{ }}x{\rm{ }}} \right)\) having \(k = 1\) and \(M = \frac{1}{{lo{g_{10}}\left( {10} \right)}}\).

Since \(f(x) = lo{g_{10}}{\rm{ }}x\) is \(O\left( {lo{g_2}{\rm{ }}x{\rm{ }}} \right)\) and\(f(x) = lo{g_{10}}{\rm{ }}x\) is \(\Omega \left( {lo{g_2}{\rm{ }}x{\rm{ }}} \right)\), so we have \(f(x) = lo{g_{10}}{\rm{ }}x\)is \(\Theta \left( {lo{g_2}{\rm{ }}x{\rm{ }}} \right)\) and,

Therefore, \(f(x) = lo{g_{10}}{\rm{ }}x\) and \(g\left( x \right) = lo{g_2}{\rm{ }}x\) have the same order.