Algorithms in a Nutshell

Performance Families | 23

AlgorithmsThe Math of

We use the following classifications exclusively in this book, and they are ordered

by decreasing efficiency:

• Constant


• Logarithmic


• Sublinear


• Linear


• n log (n)


• Quadratic


• Exponential
  We’ll now present several discussions to illustrate some of these performance
  identifications.

Discussion 0: Constant Behavior

When analyzing the performance of the algorithms in this book, we frequently

claim that some primitive operations provide constant performance. Clearly this

claim is not an absolute determinant for the actual performance of the operation

since we do not refer to specific hardware. For example, comparing whether two

32-bit numbersxandyare the same value should have the same performance

regardless of the actual values ofxandy. A constant operation is defined to have

O(1) performance.

What about the performance of comparing two 256-bit numbers? Or two 1,024-

bit numbers? It turns out that for a predetermined fixed sizek, you can compare

twok-bit numbers in constant time. The key is that the problem size (i.e., the

values of the numbersxandythat are being compared) cannot grow beyond the

fixed sizek. We abstract the extra effort, which is multiplicative in terms ofk,

with the notation O(1).

Discussion 1: Log n Behavior

A bartender offers the following $10,000 bet to any patron. “I will choose a

number from 1 to 1,000,000 and you can guess 20 numbers, one at a time; after

each guess, I will either tell you TOO LOW, TOO HIGH, or YOU WIN. If you

win in 20 questions, I give you $10,000; otherwise, you give me $10,000.” Would

you take this bet? You should because you can always win. Table 2-1 shows a

sample scenario for the range 1–10 that asks a series of questions, reducing the

problem size by about half each time.

Table 2-1. Sample behavior for guessing number from 1–10

Number First guess Second guess Third guess

1 Is it 5?

TOO HIGH

Is it 2?

TOO HIGH

Is it 1?

YOU WIN

2 Is it 5?

TOO HIGH

Is it 2?

YOU WIN

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

Licensed by

Ming Yi