Asymptotic Analysis in Practice

In this final article we will look at analysing the complexity of an algorithm without the use of asymptotic analysis, and in doing so showcase the benefits of using Big O Notation. Additionally we will look at the everyday practical uses of Big O when developing software applications.

The above code doesn’t do anything meaningful. Given an array of integers of n size, iterate through the array, and for any element equal to 5 we simply multiply it by 6 and print it.

Without asymptotic analysis how would we go about evaluating this algorithm for efficiency without performing some kind of benchmark? Well, the simple answer would be to count the amount of instructions executed. The more instructions that have to be executed the more time its going to take for the computer to finish executing that algorithm. Therefore, knowing how many instructions the algorithm is made of seems like a good starting point.

The example can be broken down into the following: a for loop that executes n times, an if statement, a multiplication, and a print statement.

A problem arises though when trying to base our performance on the number of instructions in the algorithm, our algorithm wont always execute all of them. The multiplication and print instructions only occur if the element is 5, and we cannot be sure if, or how many elements in an array will be equal to 5.

Additionally, the code we write is broken down into something that is understood by a computer. The number of instructions it is broken down into depends on the hardware and compiler. Which means our algorithm again is only being tested against a specific hardware/software configuration.

As we have already seen then asymptotic analysis removes these dependencies, allowing us to test independent of any specific implementation. In asymptotic anlaysis the constant values are ignored, this makes sense in our case as this relates to the instuctions themselves, which like we said may be different.

Therefore, we simply need to look at the algorithm and determine its order of growth. The highest power related to its input, in this case it is simply n. We loop around all of the elements once and possibly do something if we have a value of 5.

Now we can use Big O to describe this algorithms upperbound, or worst case scenario. We can say that the algorithm f(n) is worst when every element in the array is equal to 5, as we would have to execute 2 instructions for each element along with executing the if statement. We would end up with a function f(n) = 2n + 1. As we stated though, we are not concerned with constant values and we know the order of growth is n so we can simply say that our algorithm has a growth rate O(n).

Asymptotic analysis allows us to calculate the efficiency of code based on its input. The best use case for big O is when developing scalable algorithms. An algorithm that has to perform well even when its input is huge. A good example of scaleable algorithms are those related to searching for data. These have to work well for 10 elements as well as for a 100,000. We know as n gets bigger it would take more time for the algorithm, therefore an algorithm with a low order of growth will perform a lot better with large input than one with a higher growth rate.

However, this best use case scenario, may not end up being how you use asymptotic analysis. It all depends on what you end up developing. Most developers won’t be writing scalable algorithms, and instead rely on asymptotic analysis for evaluation and decision making. That is asymptotic analysis is useful at identifying bottle necks in a piece of software, and acts as a useful tool when deciding what algorithms or data structures to use to solve a given problem. Without such knowledge you will be less able to identify performance issues and are more likely to write code that causes them.

I hope this article has provided some context on the theory previously discussed, whilst showing pratical uses of asymptotic analysis. Dont worry though as you become a more experienced programmer using Big O will become second nature.