O'Reilly logo

Data Structures and Algorithms in C++, Second Edition by David M. Mount, Roberto Tamassia, Michael T. Goodrich

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 4. Analysis Tools

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required