Chapter 3: Algorithms

Suppose that you have two different algorithms for solving a problem. To solve a problem of size n, the first algorithm uses exactly \(n(\log n)\)operations and the second algorithm uses exactly \({n^{\frac{3}{2}}}\) operations. As \(n\) grows, which algorithm uses fewer operations?

Find an integernwith$\mathbf{n}\mathbf{>}\mathbf{2}$for which${\mathit{n}}^{{\mathbf{2}}^{\mathbf{100}}}\mathbf{<}{\mathbf{2}}^{\mathbf{n}}$.

An algorithm is called optimal for a solution of a problem with respect to a specified operation if there is no algorithm for solving this problem using fewer operations.

a) Show that Algorithm 1 in Section 3.1 is an optimal algorithm with respect to the number of comparisons of integers.[Note: Comparisons used for bookkeeping in the loop are not of concern here.]

b) Is the linear search algorithm optimal with respect to the number of comparisons of integers (not including comparisons used for bookkeeping in the loop)?

Suppose that you have two different algorithms for solving a problem. To solve a problem of size n, the first algorithm uses exactly \({n^2}{2^n}\)operations and the second algorithm uses exactly \(n!\) operations. As \(n\) grows, which algorithm uses fewer operations?

Describe an algorithm that determines whether a function from a finite set to another finite set is one-to-one.

Find an integer nwith$\mathit{n}\mathbf{>}\mathbf{2}$for which${\mathbf{(}\mathbf{log}\mathbf{}\mathbf{n}\mathbf{)}}^{{\mathbf{2}}^{\mathbf{100}}}\mathbf{<}\sqrt{n}$.

Describe an algorithm that will count the number of 1s in a bit string by examining each bit of the string to determine whether it is a 1 bit.

Describe the worst-case time complexity, measured in terms of comparisons, of the ternary search algorithm described in Exercise 27 of Section 3.1.

Give as good a big-O estimate as possible for each of these functions.

\(\begin{aligned}{*{20}{l}}{a){\rm{ }}\left( {{n^2}{\rm{ }} + {\rm{ }}8} \right)\left( {n{\rm{ }} + {\rm{ }}1} \right)}\\{b){\rm{ }}\left( {n{\rm{ }}log{\rm{ }}n{\rm{ }} + {\rm{ }}{n^2}} \right)\left( {{n^3}{\rm{ }} + {\rm{ }}2} \right)}\\{c){\rm{ }}\left( {n!{\rm{ }} + {\rm{ }}2n} \right)\left( {{n^3}{\rm{ }} + {\rm{ }}log\left( {{n^2}{\rm{ }} + {\rm{ }}1} \right)} \right)}\end{aligned}\)

Arrange the functions${\mathit{n}}^{\mathbf{n}}\mathbf{,}{\mathbf{(}\mathbf{log}\mathbf{}\mathit{n}\mathbf{)}}^{\mathbf{2}}\mathbf{,}{\mathit{n}}^{1.0001}\mathbf{,}{\mathbf{(}\mathbf{1}\mathbf{.}\mathbf{0001}\mathbf{)}}^{\mathbf{n}}\mathbf{,}{\mathbf{2}}^{\sqrt{log}}$₂nand$\mathbf{n}{\left(\log n\right)}^{\mathbf{1001}}$in a list so that each function is big-O of the next function. [Hint: To determine the relative size of some of these functions, take logarithms]