Problem $2.$ Mystery Algorithm $(10$ points$)$

You encounter the following pseudocode, and you can assume it calls the procedure LINEARSEARCH

implemented as we covered in class.

$($a$)$ Assume that the algorithm accepts an array of $n$ distinct integers in the range $1..n+1.$ In

English, describe what this algorithm is trying to accomplish.

Solution:

$($b$)$ Formally show the worst$-$case run$-$time $T(n)$ of the Mystery Algorithm. Assume that

each execution of the $k$ th line takes $c_k$ time where $c_k$ is a constant, and assume that

LINEARSEARCH itself takes $n$ steps.

Start by filling in the two rightmost columns of the table below.

Solution:

$($c$)$ Compute $T(n)$ based on your table above.

Solution:

$($d$)$ Give a tight bound on the run$-$time of this algorithm in the worst$-$case.

Solution:

$($e$)$ Give an example of A that would result in the best$-$case run time. Give a bound on that

run$-$time.

Solution: