Linear Search has a complexity of O(n), Selection Sort is O(n^2) and Binary Search is of O(lg n), you must have heard or read these statements a lot. But what do the terms “Complexity” and “Big O” mean?
According to Wikipedia, Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity. But that makes me more confused what does “limiting behaviour of a function” mean? Let’s investigate on this and try to understand what this mysterious thing in the field of algorithm design.
They say Linear Search has a complexity of O(n), and I know how to write a code for a linear search, here it is:
int search(int arr[], int n, int x){
for (int i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
Let’s analyse this code for Linear Search which is in C++, line 1 of this code tell us about the return type which is int, the name of the function “search” and some parameters, that will be useful to understand Big O. The first parameter “int arr[]” this is array in which we have to search the item, the second parameter, “int n” is the size of the array arr and finally, the parameter “int x” should be the item that we have to search in the given array.
At this point, we have a clue (or observation) that is the complexity of an algorithm depends on the size of the array. Because the size of the array is n (where n is some integer number like 5 or 10 or 5318008) and we know the complexity of Linear Search is O(n).
Also, by observing how we write the Big O notation, we have another clue and O is some sort of function. Which means there will be a well-defined equation for the function O. So, we can understand Big O if we find out that magic function.
Let’s continue with our investigation, on line 3, we start a for loop to read each element in the array and on line 4, we check if that element is equal to the item we wanted to search. This for loop will run until all the element is found or till the end of the array. Which leads us to the fourth clue, that is complexity depends on the number of statements executed in an algorithm (where the statement is any process done by the CPU) and it takes some time to execute each process. Maybe that is we mean by the term “Complexity”, how complex a program is. If an algorithm has fewer processes then it has less complexity and similarly if an algorithm hundreds of millions of processes then it is obviously complex.
With these clues, we can conclude that O is a function of time taken by the CPU to complete an algorithm. But that shoots us with a question, The number of processes done by CPU varies with the input parameters of the algorithm, then how can we say that the O function of an algorithm is always same?
Well, if we try to simulate a bunch of Linear Search algorithms with different input parameter the complexity is changing as we thought, but the complexity never crossed the mark of the total number of processes that algorithm had. Which gives us the next clue that is, O is the function of the maximum complexity of an algorithm that’s why the O never changes with the input parameter.
Okay, I think we have a pretty good idea of what a Big O is:
- It depends on the number of processes the CPU has to do in an algorithm
- It is the function of time taken by the CPU to run that algorithm
- It tells us the maximum complexity of an algorithm (a.k.a worst case scenario)
Let’s count the total time taken by CPU to run Linear Search algorithm,
We don’t have to count line 1 and 3 of the code because compiler conveniently writes the processes that the CPU will actually process. The CPU will process the if condition n times, 1 for each iteration of the loop and any one of the return statement because if we find the item we are searching then the return statement inside the if block will be executed and nothing will be executed after that, and if the required item is not found then the return statement in line 6 will be executed and not the return statement in line 5. Let’s assume that each process takes to time (as discussed earlier), then the total time is taken, T will be the sum of all the above-mentioned processes.
That is, T = nt + t. With this equation, we can clearly see that O(n) is nt + t. But there is still a problem, with this logic, the complexity of all algorithms must be O(n) but it’s clearly not. Where do this n^2 and n*lg(n) and lg(n) come from? To understand this we need to analyse multiple algorithms and compare the results. So, let’s do that.
Selection Sort
void swap(int *xp, int *yp){
int temp = *xp;
*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n){
int i, j, min_idx;
for (i = 0; i < n-1; i++){
min_idx = i;
for (j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
swap(&arr[min_idx], &arr[i]);
}
}
In this, T = n(n-1)t + 5t = (n^2)t -nt + 5t (You can calculate T yourself using the same method as shown above).
Merge Sort
void merge(int arr[], int l, int m, int r){
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2){
if (L[i] <= R[j]){
arr[k] = L[i];
i++;
}
else{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1){
arr[k] = L[i];
i++;
k++;
}
while (j < n2){
arr[k] = R[j];
j++;
k++;
}
}
void mergeSort(int arr[], int l, int r){
if (l < r){
int m = l+(r-l)/2;
mergeSort(arr, l, m);
mergeSort(arr, m+1, r);
merge(arr, l, m, r);
}
}
n this, T = lg(n)t + lg(n-1)t + lg(n-2)t + … + lg(1)t = lg(n(n-1)(n-2)…1)t = lg(n!)t = n*lg(n)t —- Do the math xD
I have noticed something, that in Big O notation, we take the term which has the highest degree like O(n^2) for Selection Sort and O(n*lg(n)) for Merge Sort. That solves the mystery of Big O notation.
In conclusion, Big O Notation is the measure of the complexity of an algorithm, as it says on the wikipedia page, it is a mathematical function of the maximum time taken by the CPU to complete all the process in an algorithm.
Thank You.