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

No credit card required

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

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

No credit card required