Algorithms in a Nutshell

Analysis in the Best, Average, and Worst Cases | 21

AlgorithmsThe Math of

Worst-Case

Asngrows, most problems have a greater number of potential instances of sizen.

For any particular value ofn, the work done by an algorithm or program may vary

dramatically over all the instances of sizen. For a given program and a given value

n, the worst-case execution time is the maximum execution time, where the

maximum is taken over all instances of sizen.

Paying attention to the worst case is a pessimistic view of the world. We are inter-

ested in the worst-case behavior of an algorithm because of:

The desire for an answer

This often is the easiest analysis of the complexity of an algorithm.

Real-time constraints

If you are designing a system to aid a surgeon performing open-heart surgery,

it is unacceptable for the program to execute for an unusually long time (even

if such slow behavior doesn’t happen “often”).

More formally, ifSnis the set of instancessiof sizen, andtmeasures the work

done by an algorithm on each instance, then work done by an algorithm onSnin

the worst case is the maximum oft(si) over allsi∈Sn. Denoting this worst-case

work onSnbyTwc(n), the rate of growth ofTwc(n) defines the worst-case

complexity of the algorithm.

In general, there are not enough resources to compute each individual instancesi

on which to run the algorithm to determine empirically the input problem that

leads to worst-case performance. Instead, an adversary tries to craft a worst-case

input problem given the description of an algorithm.

Average-Case

A telephone system designed to support a large numbernof telephones must, in

the worst case, be able to complete all calls wheren/2 people pick up their phones

and call the othern/2 people. Although this system will never crash because of

overload, it will be prohibitively expensive to construct. Besides, the probability

that each ofn/2 people calls a unique member of the othern/2 people is exceed-

ingly small. One could design a system that is cheaper and will very rarely

(possibly never) crash due to overload. But we must resort to mathematical tools

to consider probabilities.

For the set of instances of sizen, we associate a probability distribution Pr, which

assigns a probability between 0 and 1 to each instance such that the sum, over all

instances of sizen, of the probability of that instance is 1. More formally, ifSnis

the set of instances of sizen, then:

Pr{}si

si∈Sn

∑ =^1

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use