main-content

This book introduces the essential concepts of algorithm analysis required by core undergraduate and graduate computer science courses, in addition to providing a review of the fundamental mathematical notions necessary to understand these concepts. Features: includes numerous fully-worked examples and step-by-step proofs, assuming no strong mathematical background; describes the foundation of the analysis of algorithms theory in terms of the big-Oh, Omega, and Theta notations; examines recurrence relations; discusses the concepts of basic operation, traditional loop counting, and best case and worst case complexities; reviews various algorithms of a probabilistic nature, and uses elements of probability theory to compute the average complexity of algorithms such as Quicksort; introduces a variety of classical finite graph algorithms, together with an analysis of their complexity; provides an appendix on probability theory, reviewing the major definitions and theorems used in the book.

### Chapter 1. Introduction

Abstract
This chapter introduces the idea of measuring the algorithm performance, of basic operation counting, and of classes of algorithms. It then proceeds to discuss the difference between various classes of algorithms and their behavior with respect to the increase of the problem size.
Dana Vrajitoru, William Knight

### Chapter 2. Mathematical Preliminaries

Abstract
This chapter discusses a few mathematical functions that appear often in analysis of algorithms. In each section, fundamental properties and theorems are discussed, and are applied in examples. It starts with the floor and ceiling functions, followed by the logarithms. Next, the summation notation is discussed along with a few of the known sum, such as triangular. This section is followed by the factorials, where both the integer function and its real approximation are discussed. The last section discusses the modulo function and its C++ implementation.
Dana Vrajitoru, William Knight

### Chapter 3. Fundamental Notations in Analysis of Algorithms

Abstract
This chapter lays the foundation of the analysis of algorithms theory in terms of the big-oh, omega, and theta notations. It also covers the related topics of the little-oh and asymptotic functions. The chapter contains formal definitions of these notations, examples of how they are proved, and theorems connecting these notations to each other. Properties of the functions introduced in the previous chapter are used here to prove the relationships defined by the fundamental notations for a variety of expressions.
Dana Vrajitoru, William Knight

### Chapter 4. Recurrence Relations

Abstract
This chapter introduces this important tool used in analysis of algorithms. It starts by the formal definition of recurrence relations and discussed their classification into homogeneous and non-homogeneous and by order. It introduces the idea of a solution, of solution verification and guessing. The following sections provide a few theorems that help solving recurrence relations, followed by systematic procedures to solve first homogeneous recurrence relations, then non-homogeneous with polynomial and exponential terms. Another section is dedicated to recurrence relations involving the floor and ceiling functions. The last section surveys methods for solving recurrence relations that do not fit the previous categories and also provides a theorem for finding an upper bound of the solution.
Dana Vrajitoru, William Knight

### Chapter 5. Deterministic Analysis of Algorithms

Abstract
This chapter introduces the core of the analysis of algorithms theory, explaining the concept of basic operation, followed by traditional loop counting, and the ideas of best case and worst case complexities for both execution time and required space. A detailed analysis is provided for the classes of algorithms involving most common data structures. This chapter compares several sorting algorithms and discusses the theorem setting the lower bound for the worst-case complexity of comparison-based sorting algorithms. It also discusses algorithms with unusual and interesting proofs of their complexity, such as Euclid’s algorithm or KMP for pattern matching.
Dana Vrajitoru, William Knight

### Chapter 6. Algorithms and Probabilities

Abstract
This chapter accomplishes two goals. First, it introduces a number of algorithms of a probabilistic nature. For this, it starts with a discussion of random number generators and related functions, followed by algorithms for shuffling a collection of objects, selecting a fair sample from a collection, and simulating a probabilistic event. Second, it uses elements of probability theory to compute the average complexity of some algorithms. It starts with simpler cases, such as the linear search, where the expected value of a variable is used. It follows with more complex cases, such as the bubble sort, where the expected value of a variable is combined with loop counting. This leads to the last section where conditional probabilities are used to prove the expected complexity of the Quicksort on the average.
Dana Vrajitoru, William Knight

### Chapter 7. Finite Graph Algorithms

Abstract
This chapter introduces a variety of classical finite graph algorithms, such as are taught in upper level computer science classes, together with an analysis of their complexity. It starts with the formal definition and classification of graphs. Then it discussed implementation details and a C++ graph class example. Breadth-first and depth-first traversals are discussed and an application to counting the connected components of a graph is provided. Then Dijkstra’s algorithm is introduced, followed by Kruskal’s and Prim’s. The problems of topological sorting and maximum flow are discussed. Finally, special tours such as Hamiltonian are discussed, as well as their feasibility.
Dana Vrajitoru, William Knight

### Chapter 8. Appendix: Probability Theory

Abstract
This appendix is provided so that various theorems of probability theory can be cited where needed in the material on probabilistic analysis of algorithms.
Dana Vrajitoru, William Knight