Describing Algorithms with Big O Asymptotic Notation
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² + 3n + 5 we can see that the largest term is 2n². This means we can describe the function as having an order of growth n², O(n²).
The order of growth of a function is dependent upon its largest term. If f(n) = 2n², 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² 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.
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.
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.
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.
O(n²) (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². 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.
