When you design and analyze algorithms, you need to be able to describe how they operate and how to design them. You also need some mathematical tools to show that your algorithms do the right thing and do it efûciently. This part will get you started. Later parts of this book will build upon this base. Chapter 1 provides an overview of algorithms and their place in modern computing systems. This chapter deûnes what an algorithm is and lists some examples. It also makes a case for considering algorithms as a technology, alongside technologies such as fast hardware, graphical user interfaces, object-oriented systems, and networks. 1 The Role of Algorithms in Computing 5 1.1 Algorithms 5 1.2 Algorithms as a technology 12 2 Getting Started 17 2.1 Insertion sort 17 2.2 Analyzing algorithms 25 2.3 Designing algorithms 34 3 Characterizing Running Times 49 3.1 O-notation, ?-notation, and ‚-notation 50 3.2 Asymptotic notation: formal deûnitions 53 3.3 Standard notations and common functions 63 4 Divide-and-Conquer 76 4.1 Multiplying square matrices 80 4.2 Strassen’s algorithm for matrix multiplication 85 4.3 The substitution method for solving recurrences 90 4.4 The recursion-tree method for solving recurrences 95 4.5 The master method for solving recurrences 101 ? 4.6 Proof of the continuous master theorem 107 ? 4.7 Akra-Bazzi recurrences 115 vi Contents 5 Probabilistic Analysis and Randomized Algorithms 126 5.1 The hiring problem 126 5.2 Indicator random variables 130 5.3 Randomized algorithms 134 ? 5.4 Probabilistic analysis and further uses of indicator random variables 140 II Sorting and Order Statistics Introduction 157 6 Heapsort 161 6.1 Heaps 161 6.2 Maintaining the heap property 164 6.3 Building a heap 167 6.4 The heapsort algorithm 170 6.5 Priority queues 172 7 Quicksort 182 7.1 Description of quicksort 183 7.2 Performance of quicksort 187 7.3 A randomized version of quicksort 191 7.4 Analysis of quicksort 193 8 Sorting in Linear Time 205 8.1 Lower bounds for sorting 205 8.2 Counting sort 208 8.3 Radix sort 211 8.4 Bucket sort 215 9 Medians and Order Statistics 227 9.1 Minimum and maximum 228 9.2 Selection in expected linear time 230 9.3 Selection in worst-case linear time 23