Probabilistic Analysis of Algorithms

Consider that you want to hire an office assistant. For this you need to pay small fee to employment agency for sending each candidate for interview. Since, actually, hiring a candidate is more costly, as you have to pay substantial fee to the employment agency. So, after interviewing the new candidate, if the new is better, you will fire the previous and hire the new. you need to estimate all the fee (i.e., expenses).

Let the candidates are numbered 1 through $n$. The procedure is such that after interviewing the $i$-th candidate you are able to decide weather to hire it or not. Initially you create a dummy variable, numbered zero (0) who is less qualified than the rest of. Following is the algorithm.

On the surface, analyzing cost of this algorithm may seem very difficult from analyzing running time of, say, Mergesort. The analytical techniques used, however, are identical whether we are analyzing the number of times certain basic operations are executed.

Interviewing has low cost, say $C_i$, but hiring is expensive, say, $C_h$. Let $m$ be the number of candidates hired, the total cost associated with the algorithm is $O(C_i n + C_h m)$. No matter how many we hire, we always interview $n$ number of candidates, so cost is $C_i n$ for interviwing. Thus, what is to be found out is $C_h m$ - the hiring cost. This quantity varies with each run of the algorithm. This, above serves as a model for common computing.

Worst Case: In the worst case, we hire every one we interview. This comes when candidates come in strictly increasing order of quality (or qualification). In that case it is $C_h n$. But that is not true. So, it is natural to ask “What we expect to happen in a typical or average case?”