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