18.1. Introduction

In computer science, there often exist multiple algorithms that a programmer can choose to use or implement to solve a problem. For example, to sort an array of directly comparable values such as integers, there are some famous algorithms such as bubble sort and merge sort (see President Obama on Bubble Sort). In scenarios such as these where multiple algorithms are available, it’s important to understand the trade-offs between the different choices. One way to help us do this is to characterize an algorithm’s performance with respect to some criteria. If you’re able to characterize the performance of bubble sort and merge sort, for example, then you might discover that one is better than the other for your particular use case. This is the goal of algorithm analysis.

We will focus on:

• What it means for an algorithm to be efficient

• The concept of algorithm analysis

• Comparing algorithmic growth functions

• Asymptotic complexity

• Big-O notation