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 y1 ... yn into an initially empty dictionary and then perform n/2 membership queries
contains(xi) for numbers x1 ... xn/2. An optimal data structure to perform n insert operations followed by a single
contains(xi) operation is to insert each yj into an unordered array Y, at a total cost O(n), and then implement the
contains(xi) query with a Sequential Search of xi 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(n2). 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 ... yn and sort an array X containing x1 ... xn/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 ...