Here is the original problem:
Now consider a deterministic linear search algorithm, which we refer to as DETERMINISTIC-SEARCH. Specifically, the algorithm searches for in order, considering [1],[2],A[3]...[] until either it finds [] = or it reaches the end of the array. Assume that all possible permutations of the input array are equally likely.
(e) Suppose that there is exactly one index such that [] = . What is the average-case running time of DETERMINISTIC-SEARCH? What is the worstcase running time of DETERMINISTIC-SEARCH?
(f) Generalizing your solution to part (e), suppose that there are ≥ 1 indices such that [] = . What is the average-case running time of DETERMINISTICSEARCH? What is the worst-case running time of DETERMINISTIC-SEARCH?
Your answer should be a function of and .
I can find the answer to (f) on the website:
The worst-case running time is −+1. The average-case running time is (+1)/(+1). Let be an indicator random variable that the th element is a match. Then Pr() is 1/(+1)
Why the Pr() is like this?
Let be an indicator random variable that we have found a match after the first −+1 elements (Pr() = 1)
Thus () = (1 + 2 + ... + − + )
= 1 + =1∑− ()
= 1 + ( − ) / ( + 1)
= ( + 1) / ( + 1)
Why they split into 1 , ... , − , ?