Question

For each function in Exercise 1, determine whether that function is \(\Omega \left( x \right)\) and whether it is \(\Theta \left( x \right)\).

Short answer

a.\(f\left( x \right) = 10\)is not\(\Omega \left( x \right)\)

b.\(f\left( x \right) = 3x + 7\)is\(\Omega \left( x \right)\)and\(f\left( x \right) = 3x + 7\)is\(\Theta \left( x \right)\)

c.\(f\left( x \right) = {x^2} + x + 1\)is\(\Omega \left( x \right)\)

d.\(f\left( x \right) = 5\log x\)is not\(\Omega \left( x \right)\)

e.\(f\left( x \right) = \left( x \right)\)is\(\Omega \left( x \right)\)and\(f\left( x \right) = \left( x \right)\)is\(\Theta \left( x \right)\)

f.\(f\left( x \right) = \left( {{\raise0.7ex\hbox{$x$} \!\mathord{\left/

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

\!\lower0.7ex\hbox{$2$}}} \right)\)is\(\Omega \left( x \right)\)and\(f\left( x \right) = \left( {{\raise0.7ex\hbox{$x$} \!\mathord{\left/

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

\!\lower0.7ex\hbox{$2$}}} \right)\) is \(\Theta \left( x \right)\)

Step-by-step solution

Determine whether \(f\left( x \right) = 10\) is \(O\left( x \right)i.e.,\left| {\left. {10} \right|} \right. < M\left| {\left. x \right|} \right.\) whenever \(x > k\)  is \(\Omega \left( x \right)\) and whether it is \(\Theta \left( x \right)\).

From Exercise 1 part (a) we have:

\(f\left( x \right) = 10\)is\(O(x)\)i.e.,\(\left| {\left. {10} \right|} \right. < M\left| {\left. x \right|} \right.\)whenever\(x > k\).

Assuming\(f\left( x \right)\)is\(\Omega \left( x \right)\), then there exists a positive real number\(M\) and a real number\(k\).

Such that \(10 \ge M\left| {\left. x \right|} \right.\)

However,\(10 \ge M\left| {\left. x \right|} \right.\) when\(\frac{1}{M}\left| {\left. {10} \right|} \right. < \left| {\left. x \right|} \right.\)(let\(M\)is nonzero)

Therefore, we get a contradiction and so it is not possible that\(f\left( x \right) = 10\)is\(\Omega \left( x \right)\).

As \(f\left( x \right) = 10\) is not \(\Omega \left( x \right),f\left( x \right) = 10\) is not \(\Theta \left( x \right)\) either.

Determine whether \(f\left( x \right) = 3x + 7\) is \(O\left( x \right)i.e.,\left| {\left. {3x + 7} \right|} \right. < M\left| {\left. x \right|} \right.\) whenever \(x > k\)  is \(\Omega \left( x \right)\) and whether it is \(\Theta \left( x \right)\).

From Exercise 1 part (b) we have:

\(f\left( x \right) = 3x + 7\)is\(O(x)\)i.e.,\(\left| {\left. {3x + 7} \right|} \right. < M\left| {\left. x \right|} \right.\)whenever\(x > k\).

Assuming\(k = 7,\)then\(x > 7.\)

Consider,

\(\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}\)

Therefore, we required\(M\)to be at most\(4\). Taking\(M = 4\).

By using the definition of the Big-Omega notation,\(f\left( x \right) = 3x + 7\)is\(\Omega \left( x \right)\)with\(k = 7\)and\(M = 4\).

As \(f\left( x \right) = 3x + 7\) is \(O(x)\) and \(f\left( x \right) = 3x + 7\) is \(\Omega \left( x \right),f(x) = 3x + 7\) is also \(\Theta \left( x \right)\).

Determine whether \(f\left( x \right) = {x^2} + x + 1\) is not \(O\left( x \right)\) is \(\Omega \left( x \right)\) and whether it is \(\Theta \left( x \right)\).

From Exercise 1 part (c) we have:

\(f\left( x \right) = {x^2} + x + 1\)is not\(O(x)\).

Assuming\(k = 0\)

Consider,

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

Therefore, we required\(M\)to be at most\(1\). Taking\(M = 1\).

By using the definition of the Big-Omega notation,\(f\left( x \right) = {x^2} + x + 1\)is\(\Omega \left( x \right)\)with\(k = 0\)and\(M = 1\).

As \(f\left( x \right) = {x^2} + x + 1\) is not \(O(x)\) and \(f\left( x \right) = {x^2} + x + 1\) is not \(\Theta \left( x \right)\) either.

Determine whether \(f\left( x \right) = 5\log x\) is \(O\left( x \right)\) i.e., \(\left| {\left. {5\log x} \right|} \right. < M\left| {\left. x \right|} \right.\) whenever \(x > k\) is \(\Omega \left( x \right)\) and whether it is \(\Theta \left( x \right)\).

From Exercise 1 part (d) we have:

\(f\left( x \right) = 5\log x\)is\(O\left( x \right)\)i.e.,\(\left| {\left. {5\log x} \right|} \right. < M\left| {\left. x \right|} \right.\)whenever\(x > k\).

Assuming\(f\left( x \right)\)is\(\Omega \left( x \right)\), Thereexists a positive real number\(M\) and a real number\(k\). Such that

\(\begin{aligned}{l}\left| {\left. {5\log x} \right|} \right. \ge M\left| {\left. x \right|} \right.\\\left| {\left. {\log x} \right|} \right. \ge \frac{M}{5}\left| {\left. x \right|} \right.\end{aligned}\)

However,\(\log \left( x \right) < x,\)therefore weget a contradiction and so it is not possible that \(f\left( x \right) = 5\log x\)is\(\Omega \left( x \right)\).

As, \(f\left( x \right) = 5\log x\) is not \(\Omega \left( x \right)\), \(f\left( x \right)\) is not \(\Theta \left( x \right)\).

Determine whether \(f\left( x \right) = x\) is \(O\left( x \right)\) i.e., \(\left| {\left. {\left( x \right)} \right|} \right. < M\left| {\left. x \right|} \right.\) whenever \(x > k\) is \(\Omega \left( x \right)\) and whether it is \(\Theta \left( x \right)\).

From Exercise 1 part (e) we have:

\(f\left( x \right) = x\)is\(O\left( x \right)\)i.e.,\(\left| {\left. {\left( x \right)} \right|} \right. < M\left| {\left. x \right|} \right.\)whenever\(x > k\).

Assuming\(k = 2,\)then\(x > 2.\)

Consider,

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

Therefore, we required\(M\)to be at most\(\frac{1}{2}\). Taking\(M = \frac{1}{2}\).

By using the definition of the Big-Omega notation,\(f\left( x \right) = x\)is\(\Omega \left( x \right)\)with\(k = 2\)and\(M = \frac{1}{2}\).

As \(f\left( x \right) = x\) is \(O(x)\) and \(f\left( x \right) = x\) is \(\Omega \left( x \right),f(x) = x\) is also \(\Theta \left( x \right)\).

Determine whether \(f\left( x \right) = \left( {{\raise0.7ex\hbox{$x$} \!\mathord{\left/

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

\!\lower0.7ex\hbox{$2$}}} \right)\)is\(O\left( x \right)\)i.e.,\(\left| {\left. {\left( {{\raise0.7ex\hbox{$x$} \!\mathord{\left/

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

\!\lower0.7ex\hbox{$2$}}} \right)} \right|} \right. < M\left| {\left. x \right|} \right.\)whenever\(x > k\)is\(\Omega \left( x \right)\)and whether it is\(\Theta \left( x \right)\).

From Exercise 1 part (e) we have:

\(f\left( x \right) = \left( {{\raise0.7ex\hbox{$x$} \!\mathord{\left/

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

\!\lower0.7ex\hbox{$2$}}} \right)\)is\(O\left( x \right)\)i.e.,\(\left| {\left. {\left( {{\raise0.7ex\hbox{$x$} \!\mathord{\left/

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

\!\lower0.7ex\hbox{$2$}}} \right)} \right|} \right. < M\left| {\left. x \right|} \right.\)whenever\(x > k\).

Assuming\(k = 0,\)then\(x > 0.\)

Consider,

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

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

\!\lower0.7ex\hbox{$2$}}} \right)} \right|} \right.\\{\rm{ }} = \left( {{\raise0.7ex\hbox{$x$} \!\mathord{\left/

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

\!\lower0.7ex\hbox{$2$}}} \right)\\{\rm{ }} > {\raise0.7ex\hbox{$x$} \!\mathord{\left/

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

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

Therefore, we required\(M\)to be at most\(\frac{1}{2}\). Taking\(M = \frac{1}{2}\).

By using the definition of the Big-Omega notation,\(f\left( x \right) = \left( {{\raise0.7ex\hbox{$x$} \!\mathord{\left/

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

\!\lower0.7ex\hbox{$2$}}} \right)\)is\(\Omega \left( x \right)\)with\(k = 0\)and\(M = \frac{1}{2}\).

As\(f\left( x \right) = x\)is\(O(x)\)and\(f\left( x \right) = \left( {{\raise0.7ex\hbox{$x$} \!\mathord{\left/

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

\!\lower0.7ex\hbox{$2$}}} \right)\)is\(\Omega \left( x \right),f(x) = \left( {{\raise0.7ex\hbox{$x$} \!\mathord{\left/

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

\!\lower0.7ex\hbox{$2$}}} \right)\) is also \(\Theta \left( x \right)\).