91Ó°ÊÓ

Big- \(O,\) big-Theta, and big-Omega notation can be extended to functions in more than one variable. For example, the statement \(f(x, y)\) is \(O(g(x, y))\) means that there exist constants \(C\) , \(k_{1},\) and \(k_{2}\) such that \(|f(x, y)| \leq C|g(x, y)|\) whenever \(x>k_{1}\) and \(y>k_{2} .\) Define the statement \(f(x, y)\) is \(\Omega(g(x, y))\)

Big- \(O,\) big-Theta, and big-Omega notation can be extended to functions in more than one variable. For example, the statement \(f(x, y)\) is \(O(g(x, y))\) means that there exist constants \(C\) , \(k_{1},\) and \(k_{2}\) such that \(|f(x, y)| \leq C|g(x, y)|\) whenever \(x>k_{1}\) and \(y>k_{2} .\) Show that \(\left(x^{2}+x y+x \log y\right)^{3}\) is \(O\left(x^{6} y^{3}\right)\)

Big- \(O,\) big-Theta, and big-Omega notation can be extended to functions in more than one variable. For example, the statement \(f(x, y)\) is \(O(g(x, y))\) means that there exist constants \(C\) , \(k_{1},\) and \(k_{2}\) such that \(|f(x, y)| \leq C|g(x, y)|\) whenever \(x>k_{1}\) and \(y>k_{2} .\) Show that \(x^{5} y^{3}+x^{4} y^{4}+x^{3} y^{5}\) is \(\Omega\left(x^{3} y^{3}\right)\)

List all the steps the naive string matcher uses to find all occurrences of the pattern \(\mathrm{FE}\) in the text COVFEFE.

List all the steps the naive string matcher uses to find all occurrences of the pattern \(\mathrm{ACG}\) in the text TACAGACG.

(Requires calculus) Show that if \(c>d>0,\) then \(n^{d}\) is \(O\left(n^{c}\right),\) but \(n^{c}\) is not \(O\left(n^{d}\right) .\)

(Requires calculus) Show that if \(b>1\) and \(c\) and \(d\) are positive, then \(\left(\log _{b} n\right)^{c}\) is \(O\left(n^{d}\right),\) but \(n^{d}\) is not \(O\left(\left(\log _{b} n\right)^{c}\right)\)

(Requires calculus) Show that if \(d\) is positive and \(b>1\) then \(n^{d}\) is \(O\left(b^{n}\right),\) but \(b^{n}\) is not \(O\left(n^{d}\right) .\)

(Requires calculus) Show that if \(c>b>1,\) then \(b^{n}\) is \(O\left(c^{n}\right),\) but \(c^{n}\) is not \(O\left(b^{n}\right) .\)

Show that if there were a coin worth 12 cents, the cashier's algorithm using quarters, 12 -cent coins, dimes, nickels, and pennies would not always produce change using the fewest coins possible.