Worst-case analysis, average-case analysis, and probabilistic analysis

Problem:

This problem is about several important but related concepts: worst-case analysis, average-case analysis, and probabilistic analysis. Consider the following “hiring” algorithm:

1. Set candidate best to be unknown;
2. For each of the n candidates, do the following:
3. Interview candidate i;
4. If candidate i is better than candidate best, then hire candidate i and set best to be i;

Assume that interviewing each candidate has a cost of In and hiring a candidate has a cost of (where > in under normal circumstances).

(a) Can you give the worst case total cost of the above hiring algorithm?

(b) Assume that the candidates come to the interview in a random order, i.e., each candidate is equally likely to be the best. Specifically, candidate i has a probability of 1/i -- to be the best among the first i candidates. Can you give the average case total cost of the above hiring algorithm?

Hint: You can consider to use the “indicator random variable” , which is equal to 1 if candidate i is hired and 0 otherwise. Hence, the average number of candidates that are actually hired is equal to the “expected value” (i.e., the average) of .

Follow-Up:

(a) The worst case is that every interviewed candidate is hired. Thus, the total cost is:

(b) In this average case, the only change to the total cost is the hiring part. So let’s focus just on this part. Specifically, as given in the Hint, the average number of candidates that will be hired is:
which in turn is equal to: . A good bound for this sum is: log n. Thus, the average case hiring cost is just log n , which is much smaller than the worst case’s hiring cost.

The lesson we learn is that average case is sometimes much better than the worst case.

HW: Sorting in the daily life

Problem (10 points):

This problem is about a common daily life application of sorting. Specifically, sorting (e.g., QuickSort) is usually done before we want to search for something. For example, bank accounts are always sorted according to the account numbers in order to facilitate searching a particular account on request.

Consider, as shown above, a sorted (in ascending order) list of n numbers (assume n is a power of 2, i.e., n = (2^k) for some positive integer k ). To search for a number x in the list, we can use the following algorithm. Compare x with the number in the middle of the list (i.e., m shown above). If they are equal, then our job is done. If x is smaller than that middle number, then we repeat this search process using just the left half of the list; otherwise, we repeat this search process using just the right half of the list.

(a) Why we can use just the left half of the list if the first comparison tells us that x is smaller than

the middle number?

(b) Please express the above algorithm as a recursive method.

(c) Please give the number of comparisons needed in the worst case. Explain your answer.