According to Wikipedia, “Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation“.
In computer science, Big O notation is used to classify algorithms according to how their run time or space requirements grow as the input size grows. It’s a rudimentary tool to analyze the complexity of an algorithm.
In this article, we are going to talk about time complexities that are most acknowledged in the tech world, then we will see how the time complexity of a program is calculated and finally the we will look into the rules behind finding out the complexity of a program.
- Table of Contents
THE WHEAT AND CHESSBOARD STORY
Once upon a time there was a King lived in India, who wanted to reward a sage for his contributions to the kingdom. The King asked the wise man to name the reward that he would like to have.
The wise man wanted nothing but some wheat grains that would fill up a chess board completely. The man said,
“Give me one grain of wheat for the first square of the chessboard, two grains for the next square, four for the next, eight for the next and so on for all 64 squares, with each square having double the number of grains as the square before.“
image courtesy: Wikipedia
The King agreed and amazed that the man had asked for such a small reward. Then the King ordered his servants to put wheat grains on each square. As we know, a chessboard has 64 squares in total. If the first square is filled up with 1 (20) grain, second with 2 (21) grains, third with 4 (22) grains and so on. Eventually the final square will be filled up with 263 grains of wheat.
When we calculate, the last square would be filled up with 9223372036854776000 grains. Assuming a grain of wheat weights 0.05g, the last square would be filled up with 461,168,601,842 tonnes of wheat.
This story can be used to demonstrate how quickly exponential sequence grows. These functions are called “exponential functions” (2n) and are actually found everywhere around us – in compound interest, inflation etc.
WHAT DOES A GOOD CODE LOOK LIKE ?
People around the world started coding since 1948. Yes ! Just one year after India became independent. As Martin Fowler said, “Any fool can write code that a computer can understand. Good programmers write code that humans can understand”. A good code must be readable as well as scalable. We are not going to talk much about readable code as it has been discussing everywhere since the first computer program written. We are now discussing about scalable code.
Let’s take an example. Suppose Twitter stores the tweets of a user in an ordered fashion in an array from first to last.
["hi, my first tweet","how are you","good night","happy new year"]
Being stored in an array, Twitter application can effortlessly find out the first and the last tweets by using the indices.
array[0] //first tweet array[array.length-1] //last tweet
Since every index of an array can be accessed at a constant time, the time complexity of this operation is 1; i.e, O(1).
Later, due to some design issues, Twitter has decided to store the tweets in the form of JSON objects wherein order doesn’t come into play.
[{
"tweet": "hi, my first tweet",
"year": "2019"
}, {
"tweet": "how are you",
"year": "2015"
}, {
"tweet": "good night",
"year": "2017"
}, {
"tweet": "happy new year",
"year": "2020"
}]
Now, it has become a complex task to find out the first and the last tweets, because it’s needed to take each object and compare the value of year with that of all the other objects. Now, it’s required to form a nested loop in order to compare the tweets. Every nested loops will have a time complexity of n2; i.e, O( n2 ). See the complexity grows from a constant time to quadratic time, when the data storage design changes from one to another. So keep this in mind that both the code and the data should be in a scalable form, which should retrieve the data in a fixed time before and after the changes are made to the data structure or the underlying database.
That’s all about scalability. Now, we can talk about time complexity. We’ve already seen O(1) and O( n2 ). But that’s not enough, we need to dig in much more.
WHAT IS TIME COMPLEXITY ?
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm.
Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to differ by at most a constant factor.
Here, we are going to discuss about time complexity only. So bear in mind, wherever the term “complexity” is mentioned, it purely time complexity, not space complexity.
HOW TO FIND OUT THE COMPLEXITY ?
Let’s take the following program,
function test(array) {
let a = 30; //O(1)
a = a + 5; //O(1)
for (let i = 0; i < array.length; i++) { //O(n)
print(); //O(n)
let found = true; //O(n)
a++; //O(n)
}
return a; //O(1)
}
The above code snippet is a simple JavaScript function test() with an input parameter array. We can see the complexities written against each line, even though it’s pretty straightforward. All the assignment operations and the return statement is having a time complexity of 1 as it does not get influenced by the input parameter array. Regardless of the size of the input argument, those statements will be executed in a constant time.
And, of course, the size of the input argument will have a direct impact on the for loop and the code lies within the loop. If the array is of size 100, then the time complexity of the loop will be 100. Since the size of array is unknown and can’t be predicted, we call it n (n is just an arbitrary number, it could be k, x or y etc).
So, the main takeaway from the above code snippet is, we have three lines with a complexity of O(1) and four lines with O(n).
The complexity of the above code snippet is: 1 + 1 + 1 + n + n + n + n = 4n + 3 = O(4n+3)
RULES OF TIME COMPLEXITY
So, we have learned how to find out the complexity of a program, Great ! Before we start studying the complexity in depth, the following 4 rules must be there in our mind. We’ll discuss one by one.
1. Worst case 2. Remove constants 3. Different terms of inputs 4. Drop non-dominants
1. WORST CASE
Consider an array or list of size n. The elements in an array are usually stored in contiguous memory locations. An element in an array, which is stored at any location, can be found out in a constant time, only if we know the index of that element. Otherwise, we will have to loop through the array, compare the value of every element, and find it out. This is true for other collections like Set, List etc.
This rule says that, finding out an element from a collection, which lies at any place (first or last) doesn’t matter. We always care about the last place; i.e, worst case.
Whenever we loop through a collection, the element can be found out in 1st iteration, 2nd iteration, 3rd iteration etc., n/2th iteration or nth iteration – we just don’t care. Wherever a loop exists, we assume it has a complexity of O(n).
2. REMOVE CONSTANTS
Consider the following code snippet,
public void printItmes(String[] items) {
System.out.println(items[0]); //O(1)
int index = 0; //O(1)
int middleIndex = (int) Math.floor(items.length); //O(1)
while (index < middleIndex) { //O(n/2)
System.out.println(items[index]); //O(n/2)
index++; //O(n/2)
}
for (int i = 0; i < 100; i++) { //O(100)
System.out.println("hello"); //O(100)
}
}
The time complexity of the above code is
= O(1) + O(1) + O(1) + O(1) + O(n/2) + O(n/2) + O(n/2) + O(100) + O(100)
= O(3n/2 + 204)
This rule says, all the constants included in your Big O notation is insignificant and can be ruled out. Here, the constant value 204 can be removed as it is too small to compare with n.
O(3n/2 + 204) ≈ O(3n/2)
Likewise, if items is of large size, then n/2 or 3n/2 could not reduce the complexity of the program in a significant way, so that too can be omitted. So wherever a loop exists, the complexity of that program wouldn’t be less than O(n); i.e, linear time.
O(3n/2) ≈ O(n)
3. DIFFERENT TERMS OF INPUTS
Now, have a look at the following code snippet,
public void doSomething(String[] items1, String[] items2) {
for (String it1 : items1) {
System.out.println(it1); //O(m)
}
for (String it2 : items2) {
System.out.println(it2); //O(n)
}
}
Here, we have two different items passed to the doSomething() method as input arguments, and separate loops exist for each item.
What this rule says is, if a program processes separate input items like this, we will have to compute the complexity of every single item to the account. Let’s say, the first item is of size m, and gives a complexity of O(m), and the second item is of size n, and gives a complexity of O(n), then the overall complexity of the above code will be O(m + n).
Does it make sense ? Let’s now look at the following code snippet,
public void doSomething(String[] items1, String[] items2) {
for (String it1 : items1) { //O(m)
for (String it2 : items2) { //O(n)
System.out.println(it1 + it2); O(?)
}
}
}
The only difference here from the above one is, the loops are now in nested form, i.e, one lies within another. Then, what will be the complexity of line no. 4 ?
Yes, it is O(m * n).
If I rename m to n (keep in mind, both m and n are arbitrary variables), it can be written as,
O(n * n) = O(n2), i.e, quadratic.
Whenever a problem has multiple loops, add them if loops are in same indentation (m + n), multiply otherwise if they are in nested indentation (m * n).
4. DROP NON-DOMINANTS
The final rule says, all the non-dominant parts should be dropped from calculating the complexity. If a problem has a complexity of O(n) and O(n2), the overall complexity will be O(n + n2). Here, the non-dominant part is O(n), and the dominant part is O(n2).
i.e, O(n + n2) ≈ O(n2)
Would this be true always? Let’s consider a different scenario, wherein complexity is given in the form of a quadratic equation, O( n2 + 5n + 100).
Let’s see what will happen if n = 2,
Of course, the dominant part here would be 100 then, and as per the last rule, the non-dominant parts to be removed, i.e, n2 and 5n. But we have also seen that one of the previous rules says constants should be removed.
In Big O, we are bit worried about the scale, that is the size of input, and we need to think about the worst case too.
So, putting n = 2 is not ideal for this problem.
Suppose, n = 15 (this could be a worst case), now the dominant part n2, and we need to drop all the other non-dominant parts. Since the size of n is unknown to us, we should always go for worst cases. That is, whenever a complexity is given with some arbitrary variables (like m, n etc.), then it should be substituted with as maximum value as it can be.
Hence, O( n2 + 5n + 100) ≈ O(n2)
FREQUENTLY DISCUSSED COMPLEXITIES
Let’s now discuss about commonly said complexities with suitable examples.
O(1) – CONSTANT TIME
We’ve already discussed this complexity in one of our previous code snippets. Consider the following example,
public void printItmes(String[] items) {
System.out.println(items[0]); //O(1)
}
If an algorithm’s time complexity is constant, it means that it will always run in the same amount of time, no matter the size of input. Here, no matter how large the items, the given program can fetch the first item in a constant time, i.e O(1).
O(n) – LINEAR TIME
Linear time complexity describes an algorithm or program who’s complexity will grow in direct proportion to the size of the input data. We’ve already seen this before, and still about to discuss again.
Consider the following problem,
public void printItmes(String[] items) {
for (String item : items) {
System.out.println(item); //O(n)
}
}
Since the size of items is unknown to us, we can only assume it’s of size n. The above code iterates entire items, and prints out one by one, i.e, n times. If the input contains n items, obviously the complexity will be O(n).
O(n2) – QUADRATIC TIME
Quadratic time complexity represents an algorithm whose performance is directly proportional to the squared size of the input data set.
For example, suppose if we were given two deck of cards, which contains some random cards only in both decks. Our aim is to find out common cards available in both the decks.
In the following example you could see some alphanumeric values that represent cards. For example, 1H means 1 of Hearts, 2D means 2 of Diamonds, QC means Queen of Clubs and so on.
public class Cards {
public static void main(String... args) {
String deck1[] = {"1H", "4C", "5D", "6S", "AC", "9H", "10H", "JD", "KD"};
String deck2[] = {"AD", "1D", "2S", "JS", "8", "4C", "5D", "9H", "QH"};
Permutatino.findDuplicates(deck1, deck2);
}
public static void findDuplicates(String[] cards1, String[] cards2) {
for (String card1 : cards1) {
for (String card2 : cards2) {
if (card1.equals(card2)) {
System.out.println(card1 + " - " + card2);
}
}
}
}
}
Here, each item from the first deck is to be compared with every element of the second deck. If the first deck contains m cards, and the second deck contains n cards, then the overall complexity will be m*n. As we already discussed, if m can be renamed to n (m and n are arbitrary variables), it could be written as n * n = n2.
O(2n) – EXPONENTIAL TIME
Exponential time complexity denotes an algorithm whose growth doubles with each addition to the input data set. Let’s take the following example. It’s all about finding out the nth fibonacci number in a recursive way. This complexity starts off in a facile fashion, but will add up the complexity exponentially in each step, and will end up convoluted.
public static int fib(int n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
How could you find out the complexity of this problem? It’s quite intricate to calculate the complexity of a problem, written in recursive way. The following diagram will definitely help us out to do that.
Here, we are going to find out 7th fibonacci number. As we can see, the size of the tree exponentially grows as n increases. All the operations will be executed twice until a base case is reached (i.e, the if statement). So, the time complexity of this program is O(2n). We can either go for a traditional for loop, instead of recursion, and which will reduce the complexity to O(n).
O(log n) – LOGARITHMIC TIME
Let’s now take an example of a Perfect Binary Tree. As we know, a perfect binary tree is a type of binary tree, in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.
From the above picture, we can see the total number of nodes in a tree at a particular height / level h, is 2h.
i.e,
Total no.of nodes at h = 0 => 20 = 1
Total no.of nodes at h = 1 => 21 = 2
Total no.of nodes at h = 2 => 22 = 4
Total no.of nodes at h = 3 => 23 = 8 and etc.
Let’s check another scenario. Assume the height of the tree starts from 1. So the total number of nodes in a tree till a particular level h, is 2h – 1.
i.e,
Total no.of nodes till h = 1 => 21 – 1 = 1
Total no.of nodes till h = 2 => 22 – 1 = 3
Total no.of nodes till h = 3 => 23 – 1 = 7
We know, 32 = 25 i.e, log2(32) = 5 Likewise, # of nodes = 2h - 1 ≈ 2h (we can drop the insignificant -1) i.e, nodes = 2h ∴ log(nodes) = h (or no. of decisions) i.e, based on the height, the maximum number of decisions to be taken in order to search for a node,is log(n).
In the given tree, if we wanted to search any node, we could achieve it in maximum of 3 steps, instead of traversing the whole tree . First we check the root element, if it doesn’t match, go for right or left child, if it doesn’t match, go for their children in right or left. It’s not at all required to traverse the entire tree. At most, half of the tree is to be traversed.
Suppose if we have a tree with 8 nodes. How many times can we divide the tree into half ? 3 times right ? We can halve a tree with 8 nodes , then we have 4 elements, if we halve it again, we have 2, if we have it again, we have 1; so maximum of 3 times.
i.e, 8 = 23; log(8) = 3; ∴ the time complexity is O(3)
log(n) complexity usually comes up with divide-conquer algorithms. Searching a phone book for a particular person is also similar to that. We don’t want to search the entire phone book, we can divide or halve down the search by first letter, then by the second letter and so on.
O(n log n) – LINEARITHMIC TIME
Let’s consider an example of MergeSort algorithm. As we know, MergeSort is one of the best performing sorting algorithm. It uses some sort of recursion to arrange the given list.
MergeSort(arr, left, right):
if left > right
return
mid = (left+right)/2
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
merge(arr, left, mid, right)
end
Unlike many other sorting algorithms, MergeSort doesn’t need to compare one element with all the other elements. We will create many sub-lists from the original list during the iteration process, and the algorithm is just needed to compare one item with other items in the same list only. Still, it wanted to do the same process for all the sub-lists; i.e, O(n).
Like we already discussed in the above section for O(log n), the dividing process for MergeSort creates a tree like structure (and merging is a reverse tree), and the comparison is being performed in the tree data. As we discussed, a list contains 8 elements can be divided up into 3 times utmost; i.e, O(log n) times.
Since the sorting algorithm performs n operations on all the log n steps, the total complexity will be O(n log n).
O(n!) – FACTORIAL TIME
This is the most expensive Big O, and can be seen if we have separate loop for every single element in the input. The simplistic example for this complexity is Permutation.
Consider the following example. How many three letter words can be formed from the given string “ABC”, taking all the three letters at a time ?
public class Permutation {
public static void main(String... strings) {
String str = "ABC";
Permutation.permute(str, 0, str.length() - 1);
}
private static void permute(String str, int l, int r) {
String text = str;
if (l == r) {
System.out.println(text);
} else {
for (int i = l; i <= r; i++) {
text = swap(text, i, l);
permute(text, l + 1, r);
}
}
}
private static String swap(String str, int i, int j) {
char[] charArray = str.toCharArray();
char temp;
char[] tempArray = charArray;
temp = tempArray[i];
tempArray[i] = tempArray[j];
tempArray[j] = temp;
return String.valueOf(tempArray);
}
}
// The output will be ABC, ACB, BAC, BCA, CAB, CBA
So the answer would be 6.
The formal definition of Permutation is given below
When n & r becomes equal, then the above formula gives a factorial time complexity.
11th Hour 