An algorithm is called optimal for the 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\mathrm{.}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$)?$