Design and analysis of Algorithms, 2nd Edition

14

Efficiency of Algorithms

Objectives

After reading this chapter, you should understand:

• The meaning, need and factors affecting efficiency
• Characteristics of a Good Solution
• Significance of differentiating between Polynomial and Non-Polynomial time algorithms
• Effect of improvement in Computer Hardware on Algorithm Running Times
• Worst and Average Case Behaviour of Algorithms
• How to perform Timing Analysis of Simple Algorithms
• Recursion: its implications for efficiency
• Tail Recursion: How it dramatically improves efficiency
• Complexity Theory: The Notion of a Resource
• Complexity Classes: Tractable and Intractable Algorithms
• The Step Counting Principle: Basis for Deriving Complexity
• Execution Time: Straight Line Programs, Recursive Programs, ...