2 Analyzing Algorithms

Modified

February 25, 2026

This section introduces the analysis of time and space complexity of algorithms.

Objectives. After learning this material, you should be able to:

Relate actual code running on hardware to our model of pseudocode used for time and space analysis.
Use big-O notation to bound the time and space usage of an iterative algorithm.
Analyze time and space usage of algorithms with nested for loops.

2.1 Background

Imagine we want to sort a list of numbers. We have two algorithms. Which is faster? The answer depends on the details, for example:

What programming language is each written in?
What hardware is each running on? What is the speed of the processor, the size of the cache, the memory available, and so on?
What does the problem instance look like? For example, are the numbers already close to being sorted, or in a random order, or arranged in some pattern?

Our goal is a systematic study of algorithm performance that strikes a balance between two goals.

Our analysis should be relevant to practice, e.g. deciding which algorithm to use.
Our analysis should be generalizable: it shouldn’t only hold for one particular programming language or hardware architecture.

We will introduce a method of analysis that strikes a balance. We will analyze pseudocode that can be translated into most programming languages. The pseudocode’s commands will roughly correspond to steps that are taken on any modern CPU. Therefore, the time analysis of the psuedocode will be pretty closely related to the actual running time of an implementation of an algorithm.

2.2 Correctness of Algorithms

First, a quick note on correctness. There are two types of algorithms: correct, and incorrect. But what does it mean for an algorithm to be correct?

We will formalize the problem the algorithm is trying to solve as a mathematically well-defined function from inputs to outputs. The algorithm is correct if, for every possible input, it produces the correct output. We will often prove correctness of our algorithms, and to do so, we must always prove that they always produce the correct outputs.

2.3 Analysis of Pseudocode

Throughout the class, we will focus on algorithms written in pseudocode. Although the code will mostly look like python, it is not supposed to be a fully specified programming language, just a step-by-step description.

We will define how much time and space each operation of our pseudocode takes in theory. This will allow us to analyze the running time and space usage.

Algorithm 2.1 (Sum a list)

sum(A):
   let n = len(A)
   let s = 0
   for i = 1 to n:
      s += A[i]
   return s

We won’t worry about specific syntax, such as “let s = 0” versus some other way of initializing a variable, as long as the meaning is clear.

2.3.1 Pseudocode operations

In our pseudocode, we will generally have the following rules and operations. We will assume they take the given number of units of time, called steps, and the given amount of space.

Variables can be integers, floating-point numbers, booleans, or characters in a string. They can also be objects, such as arrays.
Declaring a variable or an array. This operation takes \(1\) step. Each variable takes \(1\) space. An array of \(n\) variables takes \(n\) space, but the array still only takes one time step to declare. We also assume that appending to an array and expanding it by one spot takes constant time.
Assigning a new value to a variable. This takes one step and no additional space.
Reading the value in a variable. This takes one step and no additional space.
Arithmetic operations such as \(+, -, *, /\). These take one step and use no space on their own. Other operations including modulo, exponentiation, and XOR are also generally allowed.
If, then, else statements. These each take one step and use no additional space on their own.
For and while loops. These take one step at each control flow location, i.e. the start and end of the loop. (We can think of them as combining an if/then/else statement with goto statements that take one step.) They use no additional space on their own.
Function calls. Calling a function takes one step and uses one space in addition to the usage of the function itself. We will not generally worry about the space usage, but it is technically important for recursive algorithms.

Example 2.1 Let us analyze the time and space usage of alg. 2.1. First, let’s look at time, or the number of steps taken to run the algorithm.

sum(A):
    let n = len(A)    # 2 steps: get length of A, store it
    let s = 0         # 1 step
    for i = 1 to n:   # 1 step each loop
       s += A[i]      # 5 steps each loop: read s,i,A[i]; add; store in s
    return s          # 1 step

Lines 2 and 3 take three steps total.

Lines 4 and 5 have a for loop. It executes \(n\) times. Each time, how many steps does it take?

During each loop, we do one step in line 4. First, we initialize i, and then, each loop, we increment i. (This may take more than one step in reality, but we will summarize it as one step – discussed below.)
During each loop, we do 5 steps in line 5.
This is a total 6 steps per loop.

Since the loop executes \(n\) times, the total number of steps taken by lines 3 and 4 is \(6n\) steps. Adding the time for lines 2, 3, and also line 6, we get a running time of \(6n+4\).

Now let’s look at space usage.

sum(A):
    let n = len(A)   # 1 space
    let s = 0        # 1 space
    for i = 1 to n:  # 1 space for i (total)
       s += A[i]     # no new space
    return s         # no new space

Summing up the space used gives a total of \(3\) space used by the algorithm. We will generally not count the input as part of the space used, although usually, it won’t matter because most algorithms use more space than the input.

Note on pseudocode conventions. Pseudocode isn’t precisely defined to follow a highly specific format; that’s part of the point. We may use slightly different notation and conventions, and you may as well. For example, in Algorithm 1, the array is 1-indexed, meaning that that first element appears at A[1], not A[0]. You may use zero-indexing if you like.

Note on realism. Our estimates here are very rough compared to reality. For example, computers can carry out additions extremely quickly compared to accessing memory storage, but here we treat both as taking the same amount of time. However, this rough approximation still turns out to usefully capture the differences in performance between algorithms much of the time.

Another simplification is that we are not considering parallelism (ability to execute multiple commands at the same time). This model can be extended to analyze parallel algorithms, but we won’t do that in this class.

Note on exact runtime. Even in an algorithm as simple as Algorithm 1, it can be a bit unclear exactly how much time and space is used down to the exact number. For example, the for loop includes an implicit branch back to the start, which we did not include in our analysis. Luckily, this won’t matter, because we are going to use big-O analysis, which will come out to the same answer regardless of these minor details. That is one of the main points of using big-O. We discuss this next.

2.4 Big-O analysis of pseudocode

Given that so many details are implementation-dependent, the running time and space usage we calculate is only approximate. For example, a slightly different analysis of Algorithm 1 could give a running time of \(7n+2\) instead of \(6n+2\).

Instead of worrying too much about this, we will “lean in” and use big-O to express the time and space usage of our algorithms. Both \(7n+2\) and \(6n+2\) are \(O(n)\), so we say the time complexity of Algorithm 1 is \(O(n)\). Similarly, the space usage is \(3 = O(1)\), meaning a constant space independent of \(n\) (remember that we are not counting the input array in the space usage).

Therefore, instead of worrying about exact constants such as \(6n\) versus \(7n\), we will worry about the asymptotic growth rate, such as linear time (\(O(n)\)) versus quadratic time (\(O(n^2)\)). So our goal is to produce a big-O summary of the time and space usage of our algorithms.

2.4.1 Conducting a big-O analysis

In order to correctly analyze algorithms, this book suggests the following approach:

Analyze the algorithm exactly, as in Example 2.1, to produce an expression such as \(6n+2\) for the time or space usage.
Use big-O to give a “simplified” big-O expression, such as \(6n + 2 = O(n)\).

Simplified expressions should look like simple functions such as \(O(n)\), \(O(n \log(n))\), \(O(n^2)\), etc. They should follow these guidelines:

Drop leading constants. For example, instead of \(O(5n^3)\), write \(O(n^3)\), which has the same meaning but is simpler.
Drop low-order terms from a summation. For example, instead of \(O(n^3 + 2n^2)\), write the simpler and equivalent \(O(n^3)\).
Simplify inside expressions where possible. For example, instead of \(O(\log(8n^3 + 5))\), write \(O(\log(n))\). (Can you prove that \(\log(8n^3 + 5) = O(\log(n))\)?)
However, avoid using an asymptotically loose upper bound. It is true that \(\log(8n^3 + 5) = O(n^2)\), but \(O(n^2)\) is too loose of a bound. The best answer here is \(O(\log(n))\).

Simplified analysis of operations. With big-O analysis, the exact number of operations per line doesn’t change the answer if it is a constant. Therefore, we can simplify our big-O analysis by pretending that every line of code that takes some constant number of steps, such as 2 or 4 or 5, only takes 1 step. This makes our arithmetic easier.

Example 2.2 We simplify the time complexity analysis of Example 2.1.

sum(A):
    let n = len(A)    # 1 step
    let s = 0         # 1 step
    for i = 1 to n:   # 1 step each loop
       s += A[i]      # 1 step each loop
    return s          # 1 step

The loop executes \(n\) times with 2 total steps per loop for a total of \(2n\). So the total is \(2n+3 = O(n)\) runtime.

While it’s not really true that s += A[i] takes one time step, it wasn’t really true that it takes 5 time steps either. The true answer depends on the machine, the context it’s running in, and other factors. This simplification still gives the right big-O time complexity.

However, be careful: not every line of code is 1 step. For example, an algorithm may include the line let s = sum(A). The sum takes \(O(n)\) time to calculate, not \(O(1)\).

2.4.2 Worst-case analysis

Algorithm 1 used the same amount of time and space regardless of the input. This is not always the case. Consider the following algorithm.

Algorithm 2.2 (Find the first nonzero element)

find_nonzero(A):
   n = len(A)
   for i = 1 to n:
      if A[i] != 0:
         return A[i]
   return "none"

Example 2.3 What is the time complexity of alg. 2.2?

find_nonzero(A):
   n = len(A)         # 1 step
   for i = 1 to n:    # 1 step per loop
      if A[i] != 0:   # 1 step per loop
         return A[i]  # 1 step if and when it executes
   return "none"      # 1 step if and when it executes

The total time usage is \(2k + 2\), where \(k\) is the number of loops that execute. But how many is that? It depends on the input array. There is no single correct answer.

To address this, we will typically use a worst-case analysis of the time and space usage of our algorithms. Here, the question is to bound the running time in the worst-case (i.e. slowest) over all possible inputs. Because the worst case is that the loop executes \(n\) times, the worst-case running time of the algorithm is \(2n+2 = O(n)\).

Unless otherwise specified, in this course, we will always be using a worst-case analysis for both time and space.

Note on input size and parameters. If we say an algorithm has running time of e.g. \(O(n)\), we must always ask carefully: what is \(n\)? In the above context, the input was a list of \(n\) numbers. So the time of the algorithm grows linearly in the size of the input. Sometimes, our input will be described by multiple parameters. For example, we may have a matrix with \(n\) rows and \(m\) columns. Our running time bound may be a function of both \(n\) and \(m\) in this case.

In computational complexity theory, we often represent the input as a string of bits that encodes the problem, and we care about running time in terms of the number of bits. That will generally not be the case for this class, though.

2.5 Examples: Nested Loops

We’ll now look at some more complex algorithms involving nested loops.

Example 2.4 (Counting equal pairs) In this problem, we are given an array A. We must count how many pairs of indices (i,j) there are such that A[i] == A[j].

Algorithm 2.3

count_equal_pairs(A):
   let n = len(A)
   let s = 0
   for i = 1 to n:
      for j = 1 to n:
         if A[i] == A[j]:
            s += 1
   return s

Exercise 2.1 Bound the asymptotic time complexity of count_equal_pairs. Show your work.

Example solution.

First, we’ll write the number of steps each instruction takes, treating any constant number as one step.

count_equal_pairs(A):
   let n = len(A)          # 1 step
   let s = 0               # 1 step
   for i = 1 to n:         # 1 step each time executed
      for j = 1 to n:      # 1 step each time executed
         if A[i] == A[j]:  # 1 step each time executed
            s += 1         # 1 step each time executed
   return s                # 1 step

To count how many times each instruction is executed, we first look at the inner for loop, which covers lines 5-7. In the worst case, line 7 is executed every time, so the loop takes 3 steps every iteration. There are n iterations of the loop.

So every time the loop on lines 5-7 runs, it takes at most 3n steps.

count_equal_pairs(A):
   let n = len(A)           # 1 step
   let s = 0                # 1 step
   for i = 1 to n:          # 1 step each time executed
      #
      # at most 3n steps
      #
   return s                 # 1 step

The for loop starting in line 4 also runs n times, and we use \(3n+1\) operations each time. This gives a total of \(n(3n+1) = 3n^2 + n\) operations coming from that for loop:

count_equal_pairs(A):
   let n = len(A)            # 1 step
   let s = 0                 # 1 step
   #
   # at most 3n^2 + n steps
   #
   #
   return s                  # 1 step

The total number of steps is \(3n^2 + n + 3 = O(n^2)\) steps, so the final answer is \(O(n^2)\).

2.5.1 Counting duplicate pairs (without double-counting)

Consider the following exercise:

Exercise 2.2 If we run alg. 2.3 on input A = [3, 5, 8, 5], what will the output be?

Solution.

It will be 6. The algorithm will find an equal pair every time i==j, i.e. at index 1, 2, 3, and 4. Then, it will find an equal pair when i==2 and j==4, i.e. A[2] == A[4] == 5. Then, it will also find an equal pair when i==4 and j==2. This adds up to 6.

Therefore, counting the number of “equal pairs” is not quite the same as counting the number of duplicates in the array without double-counting. For the example above, there is one pair of duplicates: indices i==2 and j==4, which both contain the entry 5. To avoid double-counting, we can modify our algorithm as follows.

Algorithm 2.4

count_duplicates(A):
   let n = len(A)
   let s = 0
   for i = 1 to n-1:
      for j = i+1 to n:
         if A[i] == A[j]:
            s += 1
   return s

The difference from Algorithm 3 is that now, the bounds of the for loops are different. Algorithm 3 looped over all pairs (i,j), e.g. (1,1), (1,2), (1,3), (1,4), (2,1), (2,2), (2,3), …. But here, Algorithm 4 only loops over pairs where i < j. This ensures that each pair of indices only gets considered once. For example, (1,2), (1,3), (1,4), (2,3), (2,4),….

Exercise 2.3 Bound the asymptotic runtime of alg. 2.4. Show your work.

Example solution.

Again, we start by noting that each line, on its own, is a constant-time operation.

count_duplicates(A):
   let n = len(A)         # 1 step
   let s = 0              # 1 step
   for i = 1 to n-1:      # 1 step each time
      for j = i+1 to n:   # 1 step each time
         if A[i] == A[j]: # 1 step each time
            s += 1        # 1 step each time
   return s               # 1 step

Again, we see that the inner loop, lines 5-7, uses 3 steps each time it executes. But how many times does the inner loop execute? It depends on i.

When i=1, it executes n-1 times (from j=2 up to j=n).
When i=2, it executes n-2 times (from j=3 up to j=n).
…
When i=n-1, it executes 1 time (from j=n to j=n).

In each case, we can say that it executes exactly \(n-i\) times, so the total number of steps for lines 5-7 is \(3(n-i)\).

Remark 2.1 (Not part of solution.). It never hurts to do an example. Let’s suppose n=4. Then when i=1, we take 3(4-1) = 9 steps. When i=2, we take 3(4-2) = 6 steps. When i=3, we take 3(4-3) = 3 steps. The total is 9 + 6 + 3 = 18.

With three steps each inner loop and \(n-i\) inner loops, we get:

count_duplicates(A):
   let n = len(A)            # 1 step
   let s = 0                 # 1 step
   for i = 1 to n-1:         # 1 step each time
      # take 3(n-i) steps
   return s                  # 1 step

Now, we calculate the total time of the outer for loop, which starts on line 4. We need to add up the time taken from each iteration.

i=1: \(3(n-1)\) steps
i=2: \(3(n-2)\) steps
…
i=n-1: \(3\) steps

To add up the total number of steps, the expression is: \[ 3(n-1) + 3(n-2) + \cdots + 3(1) . \] We can reverse the order of the sum to make it simpler: \[ 3(1) + 3(2) + \cdots + 3(n-1) = 3 \sum_{i=1}^{n-1} i. \] We recall from Discrete Math that the sum of \(1\) up to \(n-1\) equals \(n(n-1)/2\). Therefore, the total number of steps for the loop is \[\begin{align*} 3 \sum_{i=1}^{n-1} i &= 3 \frac{n(n-1)}{2} \\ &= \frac{3}{2}n^2 - \frac{3}{2}n . \end{align*}\]

We have reached this stage:

count_duplicates(A):
   let n = len(A)            # 1 step
   let s = 0                 # 1 step
   # take (3/2)n^2 - (3/2)n steps
   return s                  # 1 step

The total number of steps is therefore \(\frac{3}{2}n^2 - \frac{3}{2}n + 3 = O(n^2)\) steps.

Comparison with Equal Pairs. Algorithm 4 is certainly faster than Algorithm 3, since its bounds on the for loops are smaller – sometimes, much smaller. However, we ended up with the same asymptotic bound on the runtime, namely quadratic: \(O(n^2)\). In fact, Algorithm 4 takes around half the number of steps of Algorithm 3, but the “half” is a constant factor that does not ultimately affect the big-O runtime bound.

2.5.2 An example with doubling

Now we will consider an example with a “while” loop.

Example 2.5 What is the asymptotic runtime of the following algorithm? Show your work. For simplicity, you may suppose that \(n\) is a power of two, i.e. \(n = 2^m\) for some integer \(m\).

Algorithm 2.5

celebrate(n):
   k = 1
   while k <= n:
      for i = 1 to k:
         print("hip hip")
      print("hooray")
      k *= 2

Example solution.

We first consider the time taken in each line:

celebrate(n):
   k = 1                   # 1
   while k <= n:           # 1 each outer loop
      for i = 1 to k:      # 1 each inner loop
         print("hip hip")  # 1 each inner loop
      print("hooray")      # 1 each outer loop
      k *= 2               # 1 each outer loop

The inner loop executes \(k\) times and takes 2 steps each time, for a total of \(2k\).

The outer loop therefore takes \(2k+3\) time steps in each loop as a function of \(k\):

celebrate(n):
   k = 1                # 1
   while k <= n:        # 1 each outer loop
      # 2k+3 steps

Now we need to add up the total time of the outer loops. \(k\) starts at 1 and doubles until it reaches \(n\), so the time is bounded by \[\begin{align*} &\left(2(1)+3\right) + \left(2(2)+3\right) + \left(2(4)+3\right) + \cdots + \left(2(n)+3\right) \\ &= 2\left[ 1 + 2 + 4 + \cdots + n \right] + \left[ 3 + 3 + \cdots + 3 \right] . \end{align*}\] We know that \(k\) can double \(\log(n)\) times before it reaches \(n\), where the logarithm is base 2. So we have \(\log(n) + 1\) copies of “3”. We also know from Discrete Math that \(1 + 2 + 4 + \cdots + n \leq 2n\). For example, if \(n=16\), then \(1+2+4+8+16 = 31 \leq 32.\)

So our total runtime is at most \(2(2n) + 3(\log(n)+1) = 4n + 3\log(n) + 3\). Taking big-O, we get a time complexity of \(O(n)\).