When talking about general data structure design, my lecture notes talk about one of the concerns being cost of operations. As well as the individual cost, it mentions amortized cost. But then it goes on to say:

Amortized cost can be:

  • absolute (e.g. for every sequence σ of operations (O(n log n))
  • competitive (e.g. for every sequence σ of operations O(OPT(σ)))

where OPT(σ) is the optimal cost of clairvoyant algorithms

I can't really make any sense of this. Googling throws up this but I can't see the relevance to data structures more generally. Can anyone help me understand the quoted text?

  • 1
    $\begingroup$ A another typical phrase term is "an algorithm that has total information". $\endgroup$
    – Raphael
    Jan 28 '14 at 11:33

A clairvoyant algorithm is a (usually hypothetical) algorithm that can look into the future to guarantee that it makes the best possible decisions. The typical application is in so-called "online" problems, where the input must be processed as it arrives, before the whole input is known, or in other situations where an algorithm must act based on incomplete knowledge. The point is that the hypothetical clairvoyant algorithm would be able to make perfect decisions so you can use that as a benchmark to judge your real algorithm for the problem.

The example given in the page you link is for page replacement algorithms. You need to swap some page of virtual memory out to disk and, of course, you'd rather not swap out a page that's just about to be accessed. The hypothetical clairvoyant algorithm would know which page will not be needed for the longest time and will swap that one out; a real algorithm would have to estimate, for example by assuming that a page that has not been used for a long time will not be used again in the near future.

Now, you can do a comparison. Suppose you have enough physical memory to hold 1000 pages and you have a process that cycles through 1001 pages accessing them in the order 1, 2, ..., 1000, 1001, 1, 2, ... The real algorithm performs terribly in this case: when page 1001 is requested, it swaps out page 1, which is the very next page to be requested. In fact, the page the process requests is never in memory. A clairvoyant algorithm might, for example, keep pages 1–999 in memory all the time and swap in pages 1000 and 1001 as needed, giving page faults only 0.2% of the time.

Other applications of this sort of idea are things like process scheduling (in most cases, a real algorithm doesn't know what demands a process will make, so it must guess) and various auction schemes where the auctioneer uses the early bids to figure out what people are prepared to pay for an item, before selling it to the next highest bidder. The classic pop-science application is in deciding who you should marry which, for some reason, academics call the Secretary Problem. The clairvoyant algorithm would be to magically know who your ideal partner is and marry them; the best you can do in practice is to spend a few years dating and dumping people and then marry the next person you meet who is better than all the ones you dumped. (This carries the risk that you'll meet your ideal partner during the date-and-dump phase and then never meet anyone else that good; math doesn't always make your life better.)

  • $\begingroup$ It might be good to tie this (otherwise good) answer to amortised analysis. There are plenty of examples in basic data structures; the usual assumption is, of course, that we don't know future operations. $\endgroup$
    – Raphael
    Jan 28 '14 at 11:36
  • $\begingroup$ @Raphael That's a good suggestion. Unfortunately, I don't know a lot about amortized analysis: perhaps somebody else could write an answer addressing that aspect of the topic? $\endgroup$ Jan 28 '14 at 11:44
  • $\begingroup$ Simply means not a greedy algorithm. $\endgroup$ Feb 11 '20 at 14:19
  • $\begingroup$ @user2994783 No, it doesn’t mean that at all. $\endgroup$ Feb 11 '20 at 14:28
  • $\begingroup$ Excuse me your first sentence is: algorithm that can look into the future to guarantee that it makes the best possible decisions". This is against the greedy approach. Greedy approach looks at the currently available best solution. It does not care about the future. $\endgroup$ Feb 13 '20 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.