Understanding Big O Notation using Javascript examples
Many a times, software engineers are faced with computational challenges that require writing efficient and reliable algorithms. For instance, given string str write a function that takes instr as an argument and returns true if the argument is a palindrome otherwise, it returns false. To solve this problem, we need to understand forehand, what it is that can be described as a palindrome. According to dictionary.com, a palindrome is a word, number, sentence, or verse that reads the same backward or forward. Going by the definition, we can conclude that madam is a palindrome.
Please note that when determining palindrome, capitalization, punctuation, and spacing are usually ignored.
There are so many approaches we can use to arrive at a working solution for this problem. However, we are not only interested in a working solution but also an efficient one. Efficiency in this case can be looked at in terms of : -
- How long the function takes to arrive at a solution? ..and …
- How much memory space the function consumes during execution?
In this article, we are only going to explore in details question 1 which basically describes the time complexity of the big O Notation. Before that though, let’s look at two different approaches to our palindrome problem because they will be fundamental in explaining the big O Notation.
Palindrome Solution 1 (Using javascript Array)
In this solution, we are taking advantage of the inbuilt javascript data structure, Array. Using the Array.from(), we can convert string input into an array and then use the reverse() method to ensure that the array element at index 0 becomes the element at Array.length -1 index and vise versa. Finally, we return a strict equality operand === of the initial Array.toString() and the reversed Array.toString() . Basically, this returns true if the provided string is a palindrome, otherwise false.
See below
Palindrome Solution (Using for …loop)
This approach starts by splitting the str right in the middle. Then it checks if the first char is the same as the last char of the str. If the two furthermost chars are not the same, we return false right away. Otherwise, the loop continues until it reaches the middle of the str then returns true.
See below
The solution using Array looks pretty straight forward and elegant, right? Well, that may just be it but it is not the best when performance is at stake. Let’s take a look at benchmark result for the two functions as indicated below.
As you can see, the approach implemented using Array is 78.58% slower against the for…loop one. Clearly, it is evident that different approaches may take different time complexities to provide a solution to a given problem. However, it is very difficult to measure time taken for a piece of code to be executed (commonly known as runtime). This is because code execution majorly depends on the speed of the computer processor. This is why Paul Bachmann and Edmund Landau in their scientific attempt to standardize how much time and space needed for a given computer operation to complete, came up with a simple unit called the Big O Notation.
What is Big O Notation?
Big O Notation is the standard unit used to determine the complexity of a given piece of code during execution. In other words, it gives an upper bound of the complexity in the worst case, helping to quantify performance as the input size becomes arbitrarily large.The complexity can either be determined as time or computer memory. In this article, we are only interested in time complexity as a yardstick to gauge the efficiency of our algorithm. Note that the Big O notation varies with input size. This basically means that as input size grows bigger the runtime also grows relative to the size of the input.
Please take note that Big O Notation however, doesn’t in any way compute the exact time taken during code execution. Instead, it indicates the rate at which runtime grows in relation to input size.
For instance, in our example above, we can use Big O Notation to determine, the relationship between code execution time when isPalindrome(str) method is called with str = ‘madam’ and gradually increase the size of str towards infinity. We then repeat the process for the other implement of isPalindrome(str). We expect this trend to have an impact on the code runtime. The computational complexity can be represented in different types of Big O Notations as below in the order of their efficiency: -
- Constant time:
O(1) - Logarithmic Time:
O(log(n)) - Linear Time:
O(n) - Linearithmic Time:
O(nlog(n)) - Quadratic Time:
O(n²) - Cubic Time:
O(n³) - Exponential Time:
O(b^n), b > 1 - Factorial Time:
O(n!)
In the next series, we will look at all these Big O Notations, their examples as well as the properties of Big O Notation in details.
In case of any incorrect information, please fill free to highlight.
