Data Structures and Algorithms in Python

Chapter 3

Algorithm Analysis

Contents

3.1 Experimental Studies

3.1.1 Moving Beyond Experimental Analysis

3.2 The Seven Functions Used in This Book

3.2.1 Comparing Growth Rates

3.3 Asymptotic Analysis

3.3.1 The “Big-Oh” Notation

3.3.2 Comparative Analysis

3.3.3 Examples of Algorithm Analysis

3.4 Simple Justification Techniques

3.4.1 By Example

3.4.2 The “Contra” Attack

3.4.3 Induction and Loop Invariants

3.5 Exercises

In a classic story, the famous mathematician Archimedes was asked to determine if a golden crown commissioned by the king was indeed pure gold, and not part silver, as an informant had claimed. Archimedes discovered a way to perform this analysis while stepping into a bath. He noted that water spilled out of the bath in proportion to the amount of him that went in. Realizing the implications of this fact, he immediately got out of the bath and ran naked through the city shouting, “Eureka, eureka!” for he had discovered an analysis tool (displacement), which, when combined with a simple scale, could determine if the king's new crown was good or not. That is, Archimedes could dip the crown and an equal-weight amount of gold into a bowl of water to see if they both displaced the same amount. This discovery was unfortunate for the goldsmith, however, for when Archimedes did his analysis, the crown displaced more water than an equal-weight lump of pure gold, indicating ...