Asymptotic Analysis in Practice

Concepts

0_LcMMZTV76P6vD5mc

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.

screen-shot-2017-07-16-at-13-08-25.png

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.

Describing Algorithms with Big O Asymptotic Notation

Concepts

alphabet-2051685_1920.png

In the previous article we looked into techniques for determining an algorithms efficiency, specifically looking into conducting asymptotic analysis of our algorithms. Today we will look at describing our analysis using a specific type of asymptotic notation, Big O. Additionally, we will look into common classifications of algorithms in terms of describing their runtime complexity with Big O.

Asymptotic analysis can help us define the limiting behaviour of a function. For our purposes we can use it to determine the efficiency of our algorithm based on the size of the input. Asymptotic notation helps us describe the analysis of a function.

We can describe the upper bound (Big O), lower bound (Big Omega), or both with Big Theta. The focus of this article is on the discussion of Big O notation, as it is the most commonly used notation when describing algorithms in computer science.

I will save you from suffering through the formal definition of Big O, especially since its not all that helpful for our purposes. If you are interested though, you can read about it on this Wikipedia page.

Big O is a notation that describes the upperbound of our algorithm. The upperbound can be seen as the worse case scenario, measuring against some metric e.g. execution time, memory consumption, etc. The notation for Big O is written O(f(n)) read: “order n” where f(n) describes the largest term within the function.

The biggest term of a function, also known as the highest order, is simply the largest term in that function. Largest describing the term with the highest power. For example, given a function f(n) = 2n^2 + 3n + 5 we can see that the largest term is 2n^2. This means we can describe the function as having an order of growth n^2, O(n^2).

The order of growth of a function is dependent upon its largest term. If f(n) = 2n^2, and g(n) = 2n, we can say that f(n) has a larger order of growth than g(n). As the value of n increases the output of f(n) is going to be much larger than that of g(n).

There are a few things that need to be mentioned before we look at common classifications.

Firstly, just to reiterate Big O is just a form of notation for describing the upperbound of our algorithm. Asymptotic notation in general is just simply a shorthand of describing the behaviour of an algorithm. That is, if we analysed our algorithm in terms of its worst case performance we would use Big O notation denote this behaviour.

Secondly, if an algorithm is described with O(f(n)) we can assume that it will act at worse O(f(n)) but we cannot assume that it will always be of O(f(n)). Therefore, be cautious as O(f(n)) might not tell you all the information you need to know about an algorithm e.g. best/average case scenarios.

Finally, it is worth noting that Big O is a guideline and not a guarantee. For some value n with a large constant c, it might be that a quadractic algorithm may be better than a linear function in cases where n is small. For example, given f(n) = 2,000n + 50 and g(n) = 2n^2 the quadratic algorithm g(n) is more efficient than the linear algorithm f(n) despite the growth of the function being larger.

This means that asymptotic analysis only holds when the value of n is large, and if its not then you cannot assume that a function with a lower order of growth is more efficient than a larger one. Remember asymptotic analysis is only concerned with the largest term, and not its constants or any other terms

With all that out of the way we can look at how to describe certain algorithms in terms of O(f(n)). Below is a few common orders of growth. Each graph shows how execution time is affected as the value of n increases.

Screen Shot 2017-07-09 at 10.24.06.png

O(1) (constant): An algorithm that always requires the same amount of time to execute. Its order of growth is constant. Any single statement of code is constant e.g. print(“Hello World”);, int a = b – c;, etc

Screen Shot 2017-07-09 at 10.20.41

O(log n) (logarithmic): An algorithm in which the time required is dependent upon the log of the input n. Its order of growth is proportional to log n where log is to the base 2. The algorithm will typically take longer to execute as n increases, but after a certain point the input of n wont affect the execution time. An example of an algorithm of O(log n) is a binary search.

Screen Shot 2017-07-09 at 10.19.42

O(n) (linear): An algorithm in which the time required to execute is dependent upon the size of the input n. Its order of growth is proportional to n. That is, as n increases the time taken to execute the algorithm will also grow at the same rate as n. An algorithm that uses a single loop iterating n times. An example of such an algorithm is a linear search.

Screen Shot 2017-07-09 at 10.22.16

O(n^2) (quadratic): An algorithm in which time required is dependent upon the size of the input n squred. Its order of growth is proportional to n^2. That is the execution time will increase dramatically as n gets larger. A typcial exmaple is any algorithm that makes use of two loops, for instance an insertion sort.

To conclude asymptotic analysis is a means of measuring the performance of an algorithm based on its input. Big O is a form of asymptotic notation that denotes the worst case scneario of our algorithm. Hopefully this has all made some sense, but if not don’t worry, the next article will put asymptotic analysis and Big O into practice through some examples.