91Ó°ÊÓ

Give a big- \(O\) estimate for the number of operations (where an operation is an addition or a multiplication) used in this segment of an algorithm. $$ \begin{array}{c}{t :=0} \\ {\text { for } i :=1 \text { to } 3} \\ {\quad \text { for } j :=1 \text { to } 4} \\ {t :=t+i j}\end{array} $$

Determine whether each of these functions is \(O(x)\) a) \(f(x)=10\) b) \(f(x)=3 x+7\) c) \(f(x)=x^{2}+x+1\) d) \(f(x)=5 \log x\) e) \(f(x)=\lfloor x\rfloor\) f) \(f(x)=\lceil x / 2\rceil\)

Devise an algorithm that finds the sum of all the integers in a list.

Find the least integer \(n\) such that \(f(x)\) is \(O\left(x^{n}\right)\) for each of these functions. a) \(f(x)=2 x^{2}+x^{3} \log x\) b) \(f(x)=3 x^{5}+(\log x)^{4}\) c) \(f(x)=\left(x^{4}+x^{2}+1\right) /\left(x^{4}+1\right)\) d) \(f(x)=\left(x^{3}+5 \log x\right) /\left(x^{4}+1\right)\)

Describe an algorithm that takes as input a list of \(n\) distinct integers and finds the location of the largest eveninteger in the list or returns 0 if there are no even integers in the list.

Devise an algorithm to compute \(x^{n}\) , where \(x\) is a real number and \(n\) is an integer. [Hint: First give a procedure for computing \(x^{n}\) when \(n\) is nonnegative by successive multiplication by \(x,\) starting with \(1 .\) Then extend this procedure, and use the fact that \(x^{-n}=1 / x^{n}\) to compute \(x^{n}\) when \(n\) is negative. \(]\)

Show that \(x \log x\) is \(O\left(x^{2}\right)\) but that \(x^{2}\) is not \(O(x \log x)\)

What is the largest \(n\) for which one can solve within one second a problem using an algorithm that requires \(f(n)\) bit operations, where each bit operation is carried out in \(10^{-9}\) seconds, with these functions \(f(n) ?\) $$ \begin{array}{llll}{\text { a) }} {\log n} & {\text { b) } n} & {\text { c) } n \log n} \\ {\text { d) } n^{2}} & {\text { e) } 2^{n}} & {\text { f) } n !}\end{array} $$

Suppose that \(f(x), g(x),\) and \(h(x)\) are functions such that \(f(x)\) is \(O(g(x))\) and \(g(x)\) is \(O(h(x)) .\) Show that \(f(x)\) is \(O(h(x)) .\)

How much time does an algorithm take to solve a problem of size \(n\) if this algorithm uses \(2 n^{2}+2^{n}\) operations, each requiring \(10^{-9}\) seconds, with these values of \(n ?\) $$ \begin{array}{lllll}{\text { a) } 10} & {\text { b) } 20} & {\text { c) } 50} & {\text { d) } 100}\end{array} $$