Design and Analysis of Algorithms

Chapter 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

Chapter Outline

4.1 Introduction

4.2 Use of Loops

4.3 Efficiency of Algorithm

4.3.1 Removing Redundant Computations Outside Loops

4.3.2 Referencing of Array Elements

4.3.3 Inefficiency due to Late Termination

4.3.4 Early Detection of desired Output Conditions

4.4 Estimating and Specifying ...