Analysis of Algorithms

Notes on Analysis of Algorithms

For:  Students of Algorithms and Data Structures,
      Numerical Analysis, and
      Connoisseurs of Efficient Scientific Computing

ANALYSIS OF ALGORITHMS is the branch of theoretical computer science concerned with characterizing the computer resources required by an algorithm. The resources we are most often concerned with are time and memory requirements.

Abu Abd-Allah ibn Musa al'Khwarizmi, 9th century mathematician whose name gives us the word algorithm and whose writings give us the word algebra.

We wish to characterize these resource requirements as functions of one or more of the "essential parameters" (from the standpoint of the resource to be measured) describing the data operated on by the algorithm. Such parameters might include the size of an array (for example, finding the minimum entry takes time depending primarily on the number of entries in a list), the size of a number (for example, the time required to raise a real number to an integral power depends primarily on the absolute value of the exponent), and the number of processors (if a parallel computer is used).

The interesting questions in analysis of algorithms usually are concerned with values of the "essential parameters" that tend to make an algorithm run slowly -- for example, n tending to infinity, if n is the size of a list to be sorted. If n is small, even an inefficient (correct) algorithm may yield the desired result in acceptable time. However, for large n, there may be, for example, an enormous performance difference between the "Quick Sort" method and the equally correct but slower "Bubble Sort" method. The problem, roughly speaking, is to describe the running time of the algorithm as being approximately proportional to some simple function of the "essential parameters" -- for example, sorting a list of size n on a serial computer takes, on average, time proportional to

n log n when Quick Sort is used;
n² when Bubble Sort is used.

The mathematical tools needed for the analysis of running times typically include mathematical induction and related analysis of recursive relations, and tools from advanced calculus such as the relation between the definite integral and area, L'Hopital's Rule, summation of infinite series, and other limit theorems "at infinity."

, , and O are used to mean, roughly, "order at least," "order exactly," and "order at most," respectively. Specifically, let f and g be non-negative functions defined on the non-negative integers. We say

f = (g) if there are positive constants C and N such that n > N implies f(n) > C * g(n);
f = (g) if there are positive constants C1, C2, and N such that n > N implies C1 * g(n) < f(n) < C2 * g(n);
f = O(g) if there are positive constants C and N such that n > N implies f(n) < C * g(n).

Technically, , , and O are set-valued functions. It would be preferable to speak of f as a member of (g), (g), or O(g). However, the notation introduced above is by now well-established in the literature of the analysis of algorithms.

In using order notation, we generally want the argument of , , or O to be as simple as possible. For example, while both of the following statements are correct, the second is preferred:

5 n² + 3 n + log n = (5 n² + 3 n);
5 n² + 3 n + log n = (n²).

The reader should be attempt to prove the following:

Proposition 1: Suppose f(n) and g(n) are positive-valued functions for n > 0. Then

f = (g) if and only if g = O(f).
f = (g) if and only if g = (f).
f = (g) if and only if f = (g) and f = O(g).
f = (1) if and only if f is bounded by a constant. (In this case, if f(n) is the running time of an algorithm where n measures the amount of data processed by the algorithm, we say the algorithm runs in constant time.)

Proposition 2: Let f and g be positive functions defined for n > 0 such that

for some real number a > 0.

If a = 0, then f = O(g).
If a > 0, then f = (g).

Note that the converse statements in Proposition 2 are, in general, false. For example, 2 + sin n = (1), although is undefined.

In analyzing the running time of an algorithm, we generally assume that each of the following operations may be performed in (1) time:

arithmetic operations (addition, subtraction, multiplication, division, negation, exponentiation IF THE EXPONENT IS BOUNDED)
bit operations (left or right shift; bitwise AND, OR, XOR, NOT; etc.)
unary and binary boolean operations (NOT, AND, OR)
comparisons ( =, <>, <, <, >, > )
reading a unit of information from memory, or (in a parallel computer) from a message sent by an adjacent processor
writing a unit of information to memory, or (in a parallel computer) in a message sent to an adjacent processor
branching (GOTO, loop control, call upon or return from subprogram, IF or switch/CASE control)

Strictly speaking, these are not all realistic assumptions. For example, one might argue that arithmetic operations take time proportional to the number of bits used for the operands, so that, e.g., addition of integers of small absolute value is faster than addition of integers of huge absolute value. In practice, however, the above are fairly realistic, as the operations cited are both fundamental and fast, and we are usually more concerned with how the running time of an algorithm depends on the quantity of data being processed than in how it depends on the running times of elementary operations.

When it is reasonable to assume the arguments of the functions are suitably restricted, evaluation of mathematical functions such as logarithms and exponentials, trigonometric and inverse-trigonometric functions, etc., are regarded as having (1) running times. When such functions are considered to have unbounded arguments, their running times typically depend in non-constant fashion on their arguments. E.g., consider two different algorithms for computing the n-th power of a real number: one, based on repetitive multiplication by the base of the exponentiation, requires (n) time (and (1) memory); another, based on repetitive squaring, requires (log n) time (and (log n) memory).

Since a program consists of a series of instructions, we need the following rules to analyze the running time of a piece of code:

If Instruction A requires (f(n)) time and Instruction B requires (g(n)) time, then Instruction A followed by Instruction B requires (f(n)+g(n)) time.
Often, the above simplifies nicely, since
(f(n)+g(n)) = ("long-term max"{f(n), g(n)}) (*)
when the right-hand side of (*) makes sense. The reader is encouraged to prove each of the following without using (*):
- (1 + 1) = (1); (yes, 2 = (1))
- (n² + n) = (n²);
- (n + log n) = (n).
- Now prove (*) after determining the meaning of "when the right-hand side of (*) makes sense."
If the body of a loop requires (f(n)) time and the loop body is performed (g(n)) times, then completion of the loop (all its performances of the loop body) requires (f(n)*g(n)) running time.

We may obtain similar rules for and O notation.

REFERENCES

A.V. Aho, J.E. Hopcroft, and J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974

D.E. Knuth, The Art of Computer Programming I: Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968

R. Miller and L. Boxer, Algorithms Sequential and Parallel: A Unified Approach, 2nd ed., Charles River Media, Inc., Hingham, MA, 2005

Back to Boxer's Home Page