Data Structures and the Java Collections Framework, Third Edition

CHAPTER 3

Analysis of Algorithms

As notedinSection2.2, a correct method is one that satisfies its specification. In defining a method, the first goal is to make sure the method is correct, and unit testing allows us to increase our confidence in a method's correctness. But if the method's execution time or memory requirements are excessive, the method may be of little value to the application. This chapter introduces two tools for measuring a method's efficiency. The first tool provides an estimate, based on studying the method, of the number of statements executed and number of variables allocated in a trace of the method. The second tool entails a run-time analysis of the method. Both tools are useful for comparing the efficiency of methods, and the tools can complement each other.

CHAPTER OBJECTIVES

1. Be able to use Big-O (and Big-Theta) notation to estimate the time and space requirements of methods.
2. Be able to conduct run-time analyses of methods.

3.1 Estimating the Efficiency of Methods

The correctness of a method depends only on whether the method does what it is supposed to do. But the efficiency of a method depends to a great extent on how that method is defined. How can efficiency be measured? We could test the method repeatedly, with different arguments. But then the analysis would depend on the thoroughness of the testing regimen, and also on the compiler, operating system and computer used. As we will see in Section 3.2, run-time analysis can have blaring weaknesses, ...