O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required