Close
Register
Close Window

BM40A1500 Data Structures and Algorithms

Chapter 1 Algorithm Analysis

Show Source |    | About   «  0.3. Abstract Data Types   ::   Contents   ::   1.2. Comparing Algorithms  »

1.1. Chapter Introduction

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.

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. It 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 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.

   «  0.3. Abstract Data Types   ::   Contents   ::   1.2. Comparing Algorithms  »

nsf
Close Window