Algorithm Analysis

An algorithm is a clearly specified set of simple instructions to be followed to solve a problem. Once an algorithm is given for a problem and decided (somehow) to be correct, an important step is to determine how much in the way of resources, such as time or space, the algorithm will require. An algorithm that solves a problem but requires a year is hardly of any use. Likewise, an algorithm that requires a gigabyte of main memory is not (currently) useful.

In this chapter, we shall discuss

• How to estimate the time required for a program.

• How to reduce the running time of a program from days or years to fractions of a second.

• The results of careless use of recursion.

• Very efficient algorithms to raise a number to a power and to compute the greatest common divisor of two numbers.