Problem $3.$ Improving Run$-$Time $(10$ points$)$

Back to the assumption that the mystery algorithm above accepts an array of distinct integers

in the range $1..n+1.$

$($a$)$ Give complete pseudocode, in the CLRS style, for an algorithm that will always return

the same result, but with a more efficient run$-$time. $($But$,$ sorting the array first is not an

acceptable solution!$)$

Solution:

$($b$)$ Compute the worst$-$case run$-$time $T(n)$ of your algorithm, showing all your steps.

Solution:

$($c$)$ Give a tight bound on the worst case run$-$time.

Solution: