This problem uses a rough (and flawed) argument to estimate the average complexity of the auction algorithm. We assume that at each iteration, only one person submits a bid (i.e., the Gauss-Seidel version of the algorithm is used). Furthermore, every object is the recipient of a bid with equal probability (1/n), independently of the results of earlier bids. (This assumption clearly does not hold, but seems to capture somewhat the real situation where the problem is fairly dense and -scaling is used.)

(a) Show that when k objects are unassigned the average number of iterations needed to assign a new object is n/k.

b) Show that, on the average, the number of iterations is n(1+1/2+···+1/n), which can be estimated as O(n log n).

(c) Assuming that the average number of bids submitted by each person is the same for all persons, show that the average running time is O(A log n).