Data Structures and Algorithms in C++, Second Edition

Chapter 4. Analysis Tools

Contents

4.1 The Seven Functions Used in This Book	154
4.1.1 The Constant Function	154
4.1.2 The Logarithm Function	154
4.1.3 The Linear Function	156
4.1.4 The N-Log-N Function	156
4.1.5 The Quadratic Function	156
4.1.6 The Cubic Function and Other Polynomials	158
4.1.7 The Exponential Function	159
4.1.8 Comparing Growth Rates	161
4.2 Analysis of Algorithms	162
4.2.1 Experimental Studies	163
4.2.2 Primitive Operations	164
4.2.3 Asymptotic Notation	166
4.2.4 Asymptotic Analysis	170
4.2.5 Using the Big-Oh Notation	172
4.2.6 A Recursive Algorithm for Computing Powers	176
4.2.7 Some More Examples of Algorithm Analysis	177
4.3 Simple Justification Techniques	181
4.3.1 By Example	181
4.3.2 The "Contra" Attack	181
4.3.3 Induction and Loop Invariants	182
4.4 Exercises	185

The Seven Functions Used in This Book

In this section, we briefly discuss the seven most important functions used in the analysis of algorithms. We use only these seven simple functions for almost all the analysis we do in this book. In fact, sections that use a function other than one of these seven are marked with a star (*) to indicate that they are optional. In addition to these seven fundamental functions, Appendix A contains a list of other useful mathematical facts that apply in the context of data structure and algorithm analysis.

The Constant Function

The simplest function we can think of is the constant function. This is the function, ...