Chapter 3: Algorithms

Change Algorithm 3 so that the binary search procedure compares x to$a_m$at each stage of the algorithm, with the algorithm terminating if $x=a_m$. What advantage does this version of the algorithm have?

Give a big-O estimate for each of these functions. For the function \(g\)in your estimate \[f\left( x \right)\] is \[O\left( {g\left( x \right)} \right),\] use a simple function \(g\) of smallest order.

\[\begin{array}{l}a){\rm{ }}\left( {{n^3} + {n^2}log{\rm{ }}n} \right)\left( {log{\rm{ }}n + 1} \right){\rm{ }} + {\rm{ }}\left( {17{\rm{ }}log{\rm{ }}n + 19} \right)\left( {{n^3} + 2} \right)\\b){\rm{ }}\left( {{2^n} + {\rm{ }}{n^2}} \right)\left( {{n^3} + {\rm{ }}{3^n}} \right)\\c){\rm{ }}\left( {{n^n} + {\rm{ }}n{2^n} + {\rm{ }}{5^n}} \right)(n!{\rm{ }} + {\rm{ }}{5^n})\end{array}\]

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

Arrange the functions $\mathit{n}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}\mathbf{<}\mathit{n}\mathbf{(}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}{\mathbf{)}}^{\mathbf{3}\mathbf{/}\mathbf{2}}\mathbf{<}{\mathit{n}}^{\mathbf{4}\mathbf{/}\mathbf{3}}\mathbf{(}\mathit{l}\mathit{o}\mathit{g}\mathbf{}\mathit{n}{\mathbf{)}}^{\mathbf{2}}\mathbf{<}{\mathit{n}}^{\mathbf{3}\mathbf{/}\mathbf{2}}\mathbf{<}{\mathit{n}}^{\mathbf{l}\mathbf{o}\mathbf{g}\mathbf{}\mathbf{n}}\mathbf{<}{\mathbf{2}}^{\mathbf{100}\mathbf{n}}\mathbf{<}{\mathbf{2}}^{{\mathbf{n}}^{\mathbf{2}}}\mathbf{<}{\mathbf{2}}^{\mathbf{2}\mathbf{n}}\mathbf{<}{\mathbf{2}}^{\mathbf{n}\mathbf{!}}$andin 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]

Analyze the worst-case time complexity of the algorithm you devised in Exercise 29 of Section 3.1 for locating a mode in a list of nondecreasing integers.

Give a big-O estimate for each of these functions. For the function \(g\)in your estimate \(f\left( x \right)\) is \(O\left( {g\left( x \right)} \right),\) use a simple function \(g\) of smallest order.

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

The ternary search algorithm locates an element in a list of increasing integers by successively splitting the list into three sublists of equal (or as close to equal as possible) size, and restricting the search to the appropriate piece. Specify the steps of this algorithm.

Give an example of two increasing functions$\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}$and$\mathit{g}\mathbf{\left(}\mathit{n}\mathbf{\right)}$from the set of positive integers to the set of positive integers such that neither$\mathit{f}\mathbf{\left(}\mathit{n}\mathbf{\right)}$is$\mathit{O}\mathbf{\left(}\mathit{g}\mathbf{\right(}\mathit{n}\mathbf{\left)}\mathbf{\right)}$nor$\mathit{g}\mathbf{\left(}\mathit{n}\mathbf{\right)}$is$\mathit{O}\mathbf{\left(}\mathit{f}\mathbf{\right(}\mathit{n}\mathbf{\left)}\mathbf{\right)}$.

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

Analyze the worst-case time complexity of the algorithm you devised in Exercise 30 of Section 3.1 for locating all modes in a list of nondecreasing integers.