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

Get Data Structures and Algorithms in C++, Second Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.