Online versus Offline Algorithms

Dr. Dobb's Journal January 1999

Clearly, an offline program, which knows the entire sequence of requests in advance, can always perform better than an online algorithm, which must anticipate any possible future event. To see how much better, assume there is an adversary: A person making requests of your algorithm who knows the operation of the algorithm and is deliberately trying to make it perform as poorly as possible.

To evaluate memory allocation, we'll measure the total amount of system memory required to satisfy a sequence of allocations. For an online algorithm, the adversary might ask for n objects of size 1. Since the adversary knows how the allocator does this, he knows which of those n objects have the highest and lowest addresses. He can then free the remaining objects, leaving a hole of size k (which is at least as big as n). The adversary can then ask for a k+1-byte object. This object can't be placed between the two 1-byte objects, so the total memory required for this sequence of requests is at least 2k+3 bytes.

An offline algorithm, however, knows which two 1-byte objects will remain, so it can allocate them at addresses 0 and 1, and then allocate the k+1-byte object just above them. Thus the offline algorithm requires k+3 bytes of memory, which is one-half of the online algorithm's requirements.

--S.G. and I.H.