Previous   Next

Growth of Functions

Most algorithms have a primary parameter N that affects the running time most significantly. The parameter N might be the degree of a polynomial, the size of a file to be sorted or searched, the number of characters in a text string, or some other abstract measure of the size of the problem being considered: it is most often directly proportional to the size of the data set being processed. When there is more than one such parameter (for example, M and N in the union–find algorithms that we discussed in ), we often reduce the analysis to just one parameter by expressing one of the parameters as a function of the other or by considering one parameter at a time (holding the other constant) so that we can restrict ourselves to considering a single parameter N without loss of generality. Our goal is to express the resource requirements of our programs (most often running time) in terms of N, using mathematical formulas that are as simple as possible and that are accurate for large values of the parameters. The algorithms in this tutorial typically have running times proportional to one of the following functions.

1

Most instructions of most programs are executed once or at most only a few times. If all the instructions of a program have this property, we say that the program's running time is constant.

log N

When the running time of a program is logarithmic, the program gets slightly slower as N grows. This running time commonly occurs in programs that solve a big problem by transformation into a series of smaller problems, cutting the problem size by some constant fraction at each step. For our range of interest, we can consider the running time to be less than a large constant. The base of the logarithm changes the constant, but not by much: When N is 1 thousand, log N is 3 if the base is 10, or is about 10 if the base is 2; when N is 1 million, log N is only double these values. Whenever N doubles, log N increases by a constant, but log N does not double until N increases to N2.

N

When the running time of a program is linear, it is generally the case that a small amount of processing is done on each input element. When N is 1 million, then so is the running time. Whenever N doubles, then so does the running time. This situation is optimal for an algorithm that must process N inputs (or produce N outputs).

N log N

The N log N running time arises when algorithms solve a problem by breaking it up into smaller subproblems, solving them independently, and then combining the solutions. For lack of a better adjective (linearithmic?), we simply say that the running time of such an algorithm is N log N. When N is 1 million, N log N is perhaps 20 million. When N doubles, the running time more (but not much more) than doubles.

N2

When the running time of an algorithm is quadratic, that algorithm is practical for use on only relatively small problems. Quadratic running times typically arise in algorithms that process all pairs of data items (perhaps in a double nested loop). When N is 1 thousand, the running time is 1 million. Whenever N doubles, the running time increases fourfold.

N3

Similarly, an algorithm that processes triples of data items (perhaps in a triple-nested loop) has a cubic running time and is practical for use on only small problems. When N is 100, the running time is 1 million. Whenever N doubles, the running time increases eightfold.

2N

Few algorithms with exponential running time are likely to be appropriate for practical use, even though such algorithms arise naturally as brute-force solutions to problems. When N is 20, the running time is 1 million. Whenever N doubles, the running time squares!

The running time of a particular program is likely to be some constant multiplied by one of these terms (the leading term) plus some smaller terms. The values of the constant coefficient and the terms included depend on the results of the analysis and on implementation details. Roughly, the coefficient of the leading term has to do with the number of instructions in the inner loop: At any level of algorithm design, it is prudent to limit the number of such instructions. For large N, the effect of the leading term dominates; for small N or for carefully engineered algorithms, more terms may contribute and comparisons of algorithms are more difficult. In most cases, we will refer to the running time of programs simply as "linear," "N log N," "cubic," and so forth. We consider the justification for doing so in detail in .

Eventually, to reduce the total running time of a program, we focus on minimizing the number of instructions in the inner loop. Each instruction comes under scrutiny: Is it really necessary? Is there a more efficient way to accomplish the same task? Some programmers believe that the automatic tools provided by modern Java compilers can produce the best machine code or that modern VMs will optimize program performance; others believe that the best route is to implement critical methods in native C or machine code. We normally stop short of considering optimization at this level, although we do occasionally take note of how many machine instructions are required for certain operations in order to help us understand why one algorithm might be faster than another in practice.

Table 2.1. Values of commonly encountered functions

This table indicates the relative size of some of the functions that we encounter in the analysis of algorithms. The quadratic function clearly dominates, particularly for large N, and differences among smaller functions may not be as we might expect for small N. For example, N3/2 should be greater than N lg2 N for huge values of N, but N lg2 N is greater for the smaller values of N that might occur in practice. A precise characterization of the running time of an algorithm might involve linear combinations of these functions. We can easily separate fast algorithms from slow ones because of vast differences between, for example, lg N and N or N and N2, but distinguishing among fast algorithms involves careful study.

lg N

Java graphics 02icon01.gif

N

N lg N

N(lg N)2

N3/2

N2

3

3

10

33

110

32

100

7

10

100

664

4414

1000

10000

10

32

1000

9966

99317

31623

1000000

13

100

10000

132877

1765633

1000000

100000000

17

316

100000

1660964

27588016

31622777

10000000000

20

1000

1000000

19931569

397267426

1000000000

1000000000000

For small problems, it makes scant difference which method we use—a fast modern computer will complete the job in an instant. But as problem size increases, the numbers we deal with can become huge, as indicated in Table 2.1. As the number of instructions to be executed by a slow algorithm becomes truly huge, the time required to execute those instructions becomes infeasible, even for the fastest computers. Screenshot gives conversion factors from large numbers of seconds to days, months, years, and so forth; Table 2.2 gives examples showing how fast algorithms are more likely than fast computers to be able to help us solve problems without facing outrageous running times.

Screenshot Seconds conversions

The vast difference between numbers such as 104 and 108 is more obvious when we consider them to measure time in seconds and convert to familiar units of time. We might let a program run for 2.8 hours, but we would be unlikely to contemplate running a program that would take at least 3.1 years to complete. Because 210 is approximately 103, this table is useful for powers of 2 as well. For example, 232 seconds is about 124 years.

Java graphics 02fig01.gif


Table 2.2. Time to solve huge problems

For many apps, our only chance of being able to solve huge problem instances is to use an efficient algorithm. This table indicates the minimum amount of time required to solve problems of size 1 million and 1 billion, using linear, N log N, and quadratic algorithms, when we can execute 1 million, 1 billion, and 1 trillion instructions per second. A fast algorithm enables us to solve a problem on a slow machine, but a fast machine is no help when we are using a slow algorithm.

operations per second

problem size 1 million

problem size 1 billion

N

N lg N

N2

N

N lg N

N2

106

seconds

seconds

weeks

hours

hours

never

109

instant

instant

hours

seconds

seconds

decades

1012

instant

instant

seconds

instant

instant

weeks

A few other functions do arise. For example, an algorithm with N2 inputs that has a running time proportional to N3 is best thought of as an N3/2 algorithm. Also, some algorithms have two stages of subproblem decomposition, which lead to running times proportional to N log2 N. It is evident from Table 2.1 that both of these functions are much closer to N log N than to N2.

The logarithm function plays a special role in the design and analysis of algorithms, so it is worthwhile for us to consider it in detail. Because we often deal with analytic results only to within a constant factor, we use the notation "log N" without specifying the base. Changing the base from one constant to another changes the value of the logarithm by only a constant factor, but specific bases normally suggest themselves in particular contexts. In mathematics, the natural logarithm (base e = 2.71828 ...) is so important that a special abbreviation is commonly used: loge N Screenshot ln N. In computer science, the binary logarithm (base 2) is so important that the abbreviation log2 N Screenshot lg N is commonly used.

The smallest integer larger than lg N is the number of bits required to represent N in binary, in the same way that the smallest integer larger than log10 N is the number of digits required to represent N in decimal. The Java statement

for (lgN = 0; N > 0; lgN++, N /= 2) ; 


is a simple way to compute the smallest integer larger than lg N. A similar method for computing this function is

for (lgN = 0, t = 1; t < N; lgN++, t += t) ; 


This version emphasizes that 2n Screenshot N < 2n+1 when n is the smallest integer larger than lg N.

Occasionally, we iterate the logarithm: We apply it successively to a huge number. For example, lg lg 2256 = lg 256 = 8. As illustrated by this example, we generally regard log log N as a constant, for practical purposes, because it is so small, even when N is huge.

We also frequently encounter a number of special functions and mathematical notations from classical analysis that are useful in providing concise descriptions of properties of programs. Table 2.3 summarizes the most familiar of these functions; we briefly discuss them and some of their most important properties in the following paragraphs.

Our algorithms and analyses most often deal with discrete units, so we often have need for the following special functions to convert real numbers to integers:

Java graphics chic01.gifx Java graphics chic02.gif: largest integer less than or equal to x

Java graphics chic03.gifx Java graphics chic04.gif: smallest integer greater than or equal to x.

For example, Java graphics chic01.gifp Java graphics chic02.gif and Java graphics chic03.gife Java graphics chic04.gif are both equal to 3, and Java graphics chic03.giflg(N +1) Java graphics chic04.gif is the number of bits in the binary representation of N. Another important use of these functions arises when we want to divide a set of N objects in half. We cannot do so exactly if N is odd, so, to be precise, we divide into one subset with Java graphics chic01.gifN/2 Java graphics chic02.gif objects and another subset with Java graphics chic03.gifN/2 Java graphics chic04.gif objects. If N is even, the two subsets are equal in size ( Java graphics chic01.gifN/2 Java graphics chic02.gif = Java graphics chic03.gifN/2 Java graphics chic04.gif); if N is odd, they differ in size by 1 ( Java graphics chic01.gifN/2 Java graphics chic02.gif + 1 = Java graphics chic03.gifN/2 Java graphics chic04.gif). In Java, we can compute these functions directly when we are operating on integers (for example, if N Screenshot 0, then N/2 is Java graphics chic01.gifN/2 Java graphics chic02.gif and N - (N/2) is Java graphics chic03.gifN/2 Java graphics chic04.gif), and we can use floor and ceil from the java.lang.Math package to compute them when we are operating on floating point numbers.

A discretized version of the natural logarithm function called the harmonic numbers often arises in the analysis of algorithms. The Nth harmonic number is defined by the equation

Java graphics 02icon02.gif


The natural logarithm ln N is the area under the curve 1/x between 1 and N; the harmonic number HN is the area under the step function that we define by evaluating 1/x at the integers between 1 and N. This relationship is illustrated in Screenshot. The formula

Java graphics 02icon03.gif


where g = 0.57721 ... (this constant is known as Euler's constant) gives an excellent approximation to HN. By contrast with Java graphics chic03.giflg N Java graphics chic04.gif and Java graphics chic01.giflg N Java graphics chic02.gif, it is better to use the log method of java.lang.Math to compute HN than to do so directly from the definition.

Screenshot Harmonic numbers

The harmonic numbers are an approximation to the area under the curve y = 1/x. The constant g accounts for the difference between HN and ln Java graphics 02icon09.gif

Java graphics 02fig02.gif


The sequence of numbers

Java graphics 02icon04.gif


that are defined by the formula

Java graphics 02icon05.gif


are known as the Fibonacci numbers, and they have many interesting properties. For example, the ratio of two successive terms approaches the golden ratio Java graphics 02icon06.gif More detailed analysis shows that Java graphics 02icon07.gif rounded to the nearest integer.

We also have occasion to manipulate the familiar factorial function N!. Like the exponential function, the factorial arises in the brute-force solution to problems and grows much too fast for such solutions to be of practical interest. It also arises in the analysis of algorithms because it represents all the ways to arrange N objects. To approximate N!, we use Stirling's formula:

Java graphics 02icon08.gif


For example, Stirling's formula tells us that the number of bits in the binary representation of N! is about N lg N.

Table 2.3. Special functions and constants

This table summarizes the mathematical notation that we use for functions and constants that arise in formulas describing the performance of algorithms. The formulas for the approximate values extend to provide much more accuracy, if desired (see reference section).

function

name

typical value

approximation

Java graphics chic01.gifx Java graphics chic02.gif

floor function

Java graphics chic01.gif3.14 Java graphics chic02.gif = 3

x

Java graphics chic03.gifx Java graphics chic04.gif

ceiling function

Java graphics chic03.gif3.14 Java graphics chic04.gif = 4

x

lg N

binary logarithm

lg 1024 = 10

ln N

FN

Fibonacci numbers

F10 = 55

Java graphics 02icon10.gif

HN

harmonic numbers

H10 Screenshot 2.9

ln N + g

N!

factorial function

10! = 3628800

(N/e)N

lg(N!)

 

lg(100!) Screenshot 520

N lg N - 1.44N

 

e = 2.71828 ...

g = 0.57721 ...

Java graphics 02icon11.gif

ln 2 = 0.693147 ...

lg e = 1/ ln2 = 1.44269 ...

 

Most of the formulas that we consider in this tutorial are expressed in terms of the few functions that we have described in this section, which are summarized in Table 2.3. Many other special functions can arise in the analysis of algorithms. For example, the classical binomial distribution and related Poisson approximation play an important role in the design and analysis of some of the fundamental search algorithms that we consider in Chapters 14 and 15. We discuss functions not listed here when we encounter them.

Exercises

Java graphics icon01.gif 2.5 For what values of N is 10N lg N > 2N2?

Java graphics icon01.gif 2.6 For what values of N is N3/2 between N(lg N)2/2 and 2N(lg N)2?

For what values of N is 2NHN - N < N lg N +10N?

ScreenshotWhat is the smallest value of N for which log10 log10 N > 8?

ScreenshotProve that Java graphics chic01.giflg N Java graphics chic02.gif + 1 is the number of bits required to represent N in binary.

Add columns to Table 2.2 for N(lg N)2 and N3/2.

Add rows to Table 2.2 for 107 and 108 instructions per second.

Write a Java method that computes HN, using the log method of java.lang.Math.

Write an efficient Java function that computes Java graphics chic03.giflg lg N Java graphics chic04.gif. Do not use a library function.

How many digits are there in the decimal representation of 1 million factorial?

How many bits are there in the binary representation of lg(N!)?

How many bits are there in the binary representation of HN?

Give a simple expression for Java graphics chic01.giflg FN Java graphics chic02.gif.

ScreenshotGive the smallest values of N for which Java graphics chic01.gifHN Java graphics chic02.gif = i for 1 Screenshot i Screenshot 10.

Give the largest value of N for which you can solve a problem that requires at least f(N) instructions on a machine that can execute 109 instructions per second, for the following functions f(N): N3/2, N5/4, 2NHN, N lg N lg lg N, and N2 lg N.


Previous   Next
Comments