Algorithms in a Nutshell

(^32) | Chapter 2: The Mathematics of Algorithms
Discussion 5b: Less Obvious Performance Computations
In most cases, reading the description of an algorithm (as shown in ADDITION
and MULTIPLICATION) is sufficient to classify an algorithm as beinglinearor
quadratic. The primary indicator forquadratic, for example, is a nested loop struc-
ture. Some algorithms defy such straightforward analysis, however. Consider the
GCD algorithm in Example 2-5, designed by Euclid to compute the greatest
common divisor between two integers stored using arrays of digits.
Figure 2-6. Comparison of mult versus alt
Example 2-5. Euclid’s GCD algorithm
public static void gcd (int a[], int b[], int gcd[]) {
if (isZero(a)) { assign (gcd, a); return; }
if (isZero(b)) { assign (gcd, b); return; }
// ensure a and b are not modified
a = copy (a);
b = copy (b);
while (!isZero(b)) {
// last argument to subtract represents sign of result which
// we can ignore since we only subtract smaller from larger.
if (compareTo(a, b) > 0) {
subtract (a, b, gcd, new int[1]);
assign (a, gcd);
} else {
subtract (b, a, gcd, new int[1]);
assign (b, gcd);
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