Design and analysis of Algorithms, 2nd Edition

4

Iterative Algorithm Design Issues

Objectives

After reading this chapter, you should understand:

• The correct use of loops in programs
• Factors that affect the efficiency of algorithms
• How to estimate and specify execution times
• How to compare algorithms in terms of their efficiency
• The Order Notation: Big-Oh, Omega, Theta, small omega, small-Oh and their properties
• Justification for the use of Problem size as a measure
• Some Tradeoffs in algorithm design

If architects worked on the same principle as software engineering, most buildings would end up looking like the Leaning Tower of Pisa.

—David Crocker

A state-of-the-art calculation requires 100 hours of CPU time on the state-of-the-art computer, independent of the decade.

—Edward Teller ...