18.2. Algorithm Analysis Steps

Algorithm analysis can be performed relative to the amount of memory a program uses (space complexity) or the amount of CPU time required to complete the work (time complexity). The amount of CPU time is usually a more interesting issue and will be the focus of this reading. There is usually a trade-off between these two complexities.

Suppose you have a set of algorithms that all solve the same problem. To analyze each of them, we first need to do the following:

  1. Define the problem size (n); then

  2. Define the set of key processing steps.

    Think of this as identifying the units. We need to define the problem size and set of key processing steps the same way for all of the algorithms we wish to compare based on their time complexities so that it’s a fair comparison.

    To determine these time complexities, we need to do the following:

  3. Derive a timing function, T(n), that reflects the number of key processing steps in terms of the problem size.

  4. Classify T(n) into a complexity class based on the formula for the function.

That’s it! Those four steps are what you need to do to perform a time complexity analysis for an algorithm. The trickiest part is usually the third step, which is what most of this tutorial will focus on. We will have a separate tutorial that focuses exclusively on the fourth step.

18.2.1. Step 1: Defining the Problem Size

For every algorithm we want to analyze, we need to define the size of the problem. Typically, we are looking for some aspect of the problem that will affect the runtime (cause the application to run longer) if that size increases.

  • When downloading a file, the size of the problem is the size of the file. A larger file size means more bytes to download and more time.

  • When searching for a target value, the size of the problem is the size of the space to search (e.g. if finding a value in an array, the array size is the problem size). If we have more items to search, the algorithm will run longer.

  • For a sorting algorithm, the size of the problem is the number of elements to be sorted.

  • When downloading images from iTunes, the problem size is the number of images to be downloaded (or the total number of bytes).

18.2.2. Step 2: Identify the Key Processing Steps

Algorithms (or more generally functions or methods) have many operations/steps that occur if you look closely. For the purpose of analysis, instead of focusing on everything, we usually only focus on a set of key processing steps. These are the operations that we’re interested in.

  • If downloading images from iTunes, downloading a single image might be the key processing step.

  • In searching and sorting, the key processing step is usually the number of comparisons done across all elements.

Sometimes, we might focus on other operations. The key processing step ultimately depends on the problem in question. In general, this set usually comprises of operations that are expensive (i.e., take a long time or require a lot of memory) as they will dominate less expensive operations in their impact on the overall complexity of the algorithm.

18.2.3. Step 3: Analyze the Time Complexity

The goal in this step is to derive a timing function, T(n), that reflects the number of key processing steps in terms of the problem size. In other words, we want to create a function that tells us how many times the key processing steps will occur as the problem size changes.

We will outline different ways to approach this using the examples in the next section.