Correctness and Efficiency of Algorithms

Let’s take some time to dive further into the ways that we can study algorithms.

Starting with Theory — Algorithm Efficiency

Determining the efficiency of an algorithm centers around two main ideas: time and space. Generally, we want to ensure that algorithms run as fast as possible, so we often try to optimize algorithms for time. In some cases, we may also want to ensure that an algorithm uses as little memory as possible. In these cases, we would optimize for the space an algorithm uses. Cases where we need to optimize for space are less common now, so we usually focus on the time portion of algorithm analysis.

To understand the motivation behind algorithm analysis, let’s consider my earlier example of searching through a list of a value. For this problem, I proposed the following solution:

• Start at the beginning of the list
• Compare the current value to the one you are searching for
  - If you find the value, return the location of the value
  - If you reach the end of the list without finding the value, return -1
  - If you don’t find the value and more values exist in the list, proceed to the next item in the list and repeat step 2

Looking at this proposed solution, how can you verify if it is a good solution to the problem? Does this algorithm run quickly? Is there any case where the algorithm fails to produce a solution? These are the types of questions we will look to answer when we analyze algorithms.

Correctness of an Algorithm

Let’s start answering these questions by translating our algorithm steps into code. I’ll be using Python, feel free to use any language you are comfortable with.

def linearSearch(list, x):
  found = False
  i = 0
  while not found and i < len(list):
    if list[i] == x:
      found = True
    else:
      i += 1
  if not found:
    i = -1
  return i

Let’s approach the analysis of this code from two angles. The first angle will be correctness. How can we determine if this algorithm is correct for every possible input? This process can vary from problem to problem, but one common approach would be to use a loop invariant. In this approach, we start by identifying any loops in our program. For each loop, we determine the condition that is true for every iteration of the loop. For this condition, we will then show that the following three conditions are true:

• Initialization: The loop invariant is true prior to the first iteration of the loop
• Maintenance: If the invariant is true before an iteration, it remains true before the next iteration
• Termination: When the loop terminates, the invariant, along with the reason the loop terminated gives us a useful property to show the algorithm is correct

This is a lot of technical terminology, so let’s see it in action with our linear search. First, start by asking: “What is true on every iteration of the loop?”. You will usually find this answer in the loop statement itself. In our case, the following statement is true on each loop iteration: “The value of the found variable is False and the value of i is less than the length of the input list”. From here, we proceed with our properties.

• Initialization: At the start of the function, we set found to False, so this property holds. If the list provided is empty, there is nothing to search for, so our algorithm should not run. If the list has at least 1 element, the value of i, initialized to 0, will always be less than the length of the list. Therefore, the initialization property holds.
• Maintenance: On each iteration, our code will check for the value we are searching for. If the value is not found, the value of i is incremented to search the next value in the list. If the value is not found and we are not at the end of the list, the loop invariant holds and we continue to the next iteration.
• Termination: The loop terminates if either i is larger than the length of the list, or found is True. If i is larger than the length of the list, it tells us the value was not found in the list. If found is True, it tells us the value was found in the list. In both cases, we have solved our searching problem for the desired input, therefore the algorithm is correct.

You can see that this process is designed to verify each step of the algorithm. It shows that the algorithm starts, runs consistently, and ends with some solution to our problem. This type of analysis is a helpful exercise for developing solutions to problems. If you need to solve a problem, you can first consider how to initialize your code. Next, you consider what must be true as you iterate and what actions your iteration must take. Finally, you show that when the code ends, in all cases, you have a solution to your problem.

Efficiency of an Algorithm

After analyzing the correctness of an algorithm, we can start to consider the algorithm’s efficiency. Our analysis of algorithms will primarily focus on the resources an algorithm requires. Common resources to consider include time, memory, energy consumption, and bandwidth. The most common resource to measure is time, so it’s the one we will most often focus on.

There are three approaches we can use to measuring the time of an algorithm. Let’s explore our options with our linear search example. Here is the code for our algorithm:

def linearSearch(list, x):
  found = False
  i = 0
  while not found and i < len(list):
    if list[i] == x:
      found = True
    else:
      i += 1
  if not found:
    i = -1
  return i

The first approach you may consider for determining how long the algorithm takes to run sis to time the algorithm. To do this, Python provides many helpful libraries, for example, the timeit library. Let’s try employing this approach here:

import timeit

def linearSearch(list, x):
    found = False
    i = 0

    while not found and i < len(list):
        if list[i] == x:
            found = True
        else:
            i += 1

    if not found:
        i = -1
    return i

l = [1,2,3,4,5,6,7,8,9,10]
val = 10

t = timeit.Timer(lambda: linearSearch(l,10))
print(t.timeit(10000000))

This code will setup a timer for our function and run it 1000 times. It will then report the amount of time it took to complete all of the runs of the function. As an example, I’ve defined a 10-element list and I’m searching for the last element in this list. I ran this 5 times and got the following 5 runtimes:

• 6.060568624998268
• 6.027344125002855
• 5.972423582999909
• 5.967676791995473
• 6.051337582997803

From these results, you should note a few details:

• My runtime and your runtime are likely different. Depending on hardware, operating system, computer load, and other factors, runtime may fluctuate
• Each time we run the code; we get a different result.

Our goal is to get an objective measure of how long it takes for our algorithm to run. This analysis should not depend on hardware or implementation details. Knowing this, measure actual time doesn’t look to be a great approach to analyzing our algorithm. So, how can we measure the time an algorithm takes in a more objective way?

Another approach we can consider is to count the number of basic operations an algorithm requires. We consider an operation to be a basic operation if it takes a constant amount of time to execute. Examples of basic operations include arithmetic, logical operators, and data access or storage. Since each operation takes a constant amount of time to complete, one operation can act as a time unit for our algorithms. This gives us an easy way to compare and contextualize the runtime of an algorithm. For example, if one algorithm takes 20 operations to complete and another takes 30 operations to complete, we can conclude that the 20 operation algorithm finishes faster than the 30 operation algorithm.

Let’s look at a few simple examples of this:

def sum(x,y):
    return x + y

When the sum function runs, we see 2 operations. The first operation is to add x and y, and the second operation is to return the result. No matter what input we provide to this function, we always have two operations. Sometimes however, the number of operations varies based on the input. For example:

def sumTwice(l):
    sum = 0

    for x in l:
        sum += x

    return sum

In this example, we start with 1 operation, setting sum to 0. Next, we have a loop. Inside the loop, there are two operations. We need to add sum to x, then we need to store the result in sum. These two operations repeat for every element in l. If we represent the length of the list as n, we have 2n operations total in the loop. Finally, we have one operation to return our sum.

In this case, the number of operations can be represented as a function of the input. We have f(n) = 2n+2 operations, where n is the size of the input list, l.

The idea of measuring operations instead of time solves the problem of time varying by computer. This property is ideal, but there are still some difficulties with this approach. For one, the types of operations that are basic are not explicitly defined. What is considered a basic operation for one processor may not be for another. Additionally, this measure can differ based on implementation detail. Take the following code for example

def sumTwice(l):
    sum = 0

    for x in l:
            sum += x

    return sum

def sumTwice2(l):
    sum = 0
    i = 0
    
    while i < len(l):
        sum += x
        i += 1

    return sum

These two functions do the exact same thing, however the while loop implementation has more operations. We need to set i to 0, which is one operation, and we need to increment i on each iteration, which is 2 operations. The runtime for this function looks more like f(n) = 4 + 4n. When we compare this to our for loop implementation, we see it is f(n) = 2 + 2n. Now both of these functions differ by some constants, but they both grow at the same rate. As the input size increases, the time to run increases linearly.

This brings us to our third and ideal approach. Rather than measuring every operation individually, we instead look at how the time to run grows based on the input size. This lets us pay less attention to small constant differences between runtimes and focus on the overall growth. Rather than saying an algorithm requires f(n) = 4+4n operations, we say algorithm runtime grows linearly proportional to the input size.

To go down this path, we need to address the idea of input size briefly. Input size differs based on the algorithm we are discussing. In our examples so far, the length of our list contributed most to the time an algorithm takes. In some cases, this may instead be the size of an integer, or the number of nodes in a data structure. We will see many different types of size as we explore new algorithms, for now just consider that size is not always the length of something.

To learn more about DSA in Python, check out our free Python DSA course.

Now that we are comfortable with the idea of rate of growth, we can more formally explore the idea of rates of growth for functions, covered in the next article.