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 |
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 simplest function we can think of is the constant function. This is the function, ...
No credit card required