Algorithm Analysis

This chapter introduces the motivation, basic notation, and fundamental techniques of algorithm analysis. We focus on a methodology known as asymptotic algorithm analysis, or simply asymptotic analysis. Asymptotic analysis attempts to estimate the resource consumption of an algorithm.

• Problems, Algorithms, and Programs
  • Problems
  • Algorithms
  • Programs
  • Summary
• Comparing Algorithms
  • Basic operations and input size
  • Growth Rates
• Best, worst, and average cases
• Asymptotic Analysis and Upper Bounds
  • Big-O Notation
  • Using summation facts
  • Pitfall: Confusing upper bound and worst case
• Lower Bounds
• Theta Notation
  • Classifying Functions
  • Pitfall: Confusing lower bound and best case

How long will it take to process the company payroll once we complete our planned merger? Should I buy a new payroll program from vendor X or vendor Y? If a particular program is slow, is it badly implemented or is it solving a hard problem? Questions like these ask us to consider the difficulty of a problem, or the relative efficiency of two or more approaches to solving a problem.

Asymptotic analysis allows us to compare the relative costs of two or more algorithms for solving the same problem. Asymptotic analysis also gives algorithm designers a tool for estimating whether a proposed solution is likely to meet the resource constraints for a problem before they implement an actual program. After reading this chapter, you should understand

• the concept of a growth rate, the rate at which the cost of an algorithm grows as the size of its input grows;

• the concept of an upper bound and lower bound for a growth rate, and how to estimate these bounds for a simple program, algorithm, or problem; and

• the difference between the cost of an algorithm (or program) and the cost of a problem.

The chapter concludes with a brief discussion of the practical difficulties encountered when empirically measuring the cost of a program, and some principles for code tuning to improve program efficiency.

You have attempted of activities on this page