An introduction to Theoretically Evaluating Algorithm Efficiency with Asymptotic Notation

Don’t get scared away by the title; what we are going to talk about isn’t all that complicated. In a previous post I introduced the concept of an algorithm, and gave a brief description into how an algorithm is deemed to be efficient. This article will take this further by discussing techniques available to us for testing the efficiency of our algorithms before we go about implementing them in code.

Before we get started, lets first go back over efficiency. An algorithm can be efficient if it meets the memory or running time requirements imposed. Basically, our algorithm must use less than a maximum amount of memory, or run no slower than an amount of time specified. The restrictions imposed are dependent up on the problem we are trying to solve.

In order to test for efficiency, an algorithm must go through a theoretical analysis, using asymptotic analysis, before the algorithm is implemented.

The reason for this theoretical analysis is that simply without it our algorithms could only be tested through implementation.

Why is this bad? Well, firstly, we have to perform the implementation before we have any idea of how the algorithm will run. Meaning you could spend a long time developing something to realise that this algorithm will not run the way you want it to.

Secondly, by testing an algorithm through implementation we are making our algorithm dependent upon a specific platform, programming language, and hardware configuration. Altering any of these variables could result in a different result. Given the shear amount of variation we could never test our algorithm for all possible configurations.

Having a way of analysing our algorithm before we start implementing it allows us to save time, but more importantly allows us to judge efficiency independent of any hardware or software.

As described by Wikipedia, asymptotic analysis is the field of mathematics for describing the limiting behaviour of functions. A limit of a function is the value a function approaches as the input of that function approaches some value, usually zero or infinity.

Therefore, we are looking at the output of our function against a specific value, based on the values we are passing into the function.

If we have the function f(x) = e^x we could look at the output of that function as x tends towards infinity. Basically our function output grows exponentially as the value of x gets larger.

Asymptotic notation is a language that describes the type of behaviour of a function respective to the growth of that function. What I mean by this is that given a function f(n) = 2n² + 600n + 200 we are only concerned with the most significant term, n², because as n tends towards infinity the other terms and constants become irrelevant, as shown in the graph below.

As you can see from the graph the n² term results in a significantly larger output as the input size increases.

There are a few different types of notation and in the next article we will go into a lot more detail about one of them, but for now lets talk about how all this relates back to algorithms.

This idea can be applied to our algorithms, whereby the input of our function is the size of our input of the algorithm. Input is the metric we use as algorithms are designed to work with inputted data because an algorithm is useless without it. A search algorithm requires elements in which to search, as does a sorting algorithm needs input to sort.

As the input increases in size we can see that an algorithm might take longer to complete, or require more memory. It would take a lot less CPU cycles, or steps to search through a 100 items as it would do to search through 100,000.

This leads us onto the output of our function, which is what we want to measure for within our algorithm. If we are measuring the time it takes to run then we would like to see how long our algorithm takes to complete as the input amount increases. If we want to measure against memory, we would want to see how much memory is used up as the amount of input increases.

Therefore asymptotic analysis is required to measure the running time or memory capacity required by our algorithms as the input size increases. Asymptotic notation is where we describe our function as a rate of growth using the most significant term, and removing any insignificant terms or constants. We end up with an independent method for determing the efficiency of an algorithm.

In the next article we will look at a specific form of asymptotic notation, Big O notation, which is commonly used in computer science for measuring an algorithms performance.