Algorithms in a Nutshell

Offline Algorithms

We may batch instances of a problem to be solved all at once, as opposed to the more usual assumption of online algorithms, in which each instance must be solved as soon as it is presented.

As an example of the improvements in allowing offline algorithms, assume we intend to implement a dictionary in which we insert a set of n numbers y₁ ... y_n into an initially empty dictionary and then perform n/2 membership queries contains(x_i) for numbers x₁ ... x_n/2. An optimal data structure to perform n insert operations followed by a single contains(x_i) operation is to insert each y_j into an unordered array Y, at a total cost O(n), and then implement the contains(x_i) query with a Sequential Search of x_i in array Y at a worst-case cost of O(n). The total worst-case cost of the n+1 operations is O(n).

Performing a sequence of n/2 executions of Sequential Search incurs a total cost of O(n²). Since there is no way to predict the queries that are to be performed, an online algorithm cannot proactively take steps to minimize the costs of a specific future query (note that an adversary can always thwart such speedup attempts). However, if we batch the sequence of n/2 contains queries for offline processing, then we could sort the array Y containing y1 ... y_n and sort an array X containing x₁ ... x_n/2, each at a worst-case cost of O(n log n), and then scan the two sorted arrays to seek duplicates, at a worst-case cost of O(n). By permitting an offline algorithm to batch the n/2 ...