Time Complexity of the Algorithms.

In computer science, analysis of algorithms is a very crucial part. It is important to find the most efficient algorithm for solving a problem. It possible to have many different algorithms to solve a problem, but the challenge here is to choose the most efficient one. Now the point is how can we recognize the most efficient algorithm if we have a set of different algorithms? Here, the concept of space and time complexity of algorithms comes into existence. Space and time complexity acts a measurement scale for algorithms.We compare the algorithms in terms of their space(amount of memory) and time complexity(number of operations).

The total amount of the computer memory used by an algorithm when it is executed, is the space complexity of that algorithm. We’ll not discuss space complexity in this article(to make this article a little bit smaller). So, the time complexity is the number of operations an algorithm performs to complete its task(considering that each operation takes the same amount of time). The algorithm who performs the task in less number of operations is considered to be the efficient one in terms of the time complexity. However, the space and time complexity is also effected by the factors such as operating system, hardware but we are not including them.

Now in order to understand the time complexity we will take an example in which we’ll compare two different algorithms which are used to solve a particular problem.

The problem is searching. We have to search for an element in an array(in this problem we are going to assume that the array is sorted in ascending order). To solve this problem we have two algorithms :

1. Linear Search.
2. Binary Search.

Let’s say the array contains ten elements and we have to find the number ten in the array.

const array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const search_digit = 10;

Linear search algorithm will compare each element of the array to the search_digit and when it finds the search_digit in the array it will return true. Now let’s count the number of operation it performs. Here, the answer is 10(since, it compares every element of the array). So, the Linear search uses ten operations to find the given element(these are the maximum number of operations for this array in the case of Linear search, this is also known as the worst case of an algorithm). In general, the Linear search will take n number of operations in its worst case(where n is the size of the array).

Let’s examine Binary search algorithm for this case.

Binary search can be easily understood by this diagram:

Binary Search

If we try to apply this logic on our problem then, first we’ll compare search_digit with the middle element of the array, that is 5. Now since, 5 is less than 10 then we will start looking for the search_digit in the array elements greater than 5, in the same way until we get the desired element 10.

Now, try to count the number of operations binary search took to find the desired element. It took approximately four operations. Now, this was the worst case for binary search. This shows that there is a logarithmic relation between number of operations performed and total size of array.

number of operations = log(10) = 4(approx)

for base 2

We can generalize this result for Binary search as:

For an array of size n , the number of operations performed by the Binary Search is: log(n)

Big O notation

In the above statements, we saw that for an array of size n , linear search will perform n operations to complete the search, whereas , Binary search performed log(n) number of operations (both for their worst cases). We can represent this as a graph ( x-axis : number of elements, y-axis : number of operations).

Time complexity of Binary search and Linear search.

This is quiet clear from the figure that the rate by which the complexity increases for Linear search is much faster than that for binary search.

When we analyse an algorithm, we use a notation to represent its time complexity and that notation is Big O notation.

For Example: time complexity for Linear search can be represented as O(n) and O(log n) for Binary search, where, n and log(n) are the number of operations.

The Time complexity or Big O notation for some popular algorithms is listed below:

1. Binary Search: O(log n)
2. Linear Search: O(n)
3. Quick Sort: O(n*log n)
4. Selection Sort: O(n*n)
5. Travelling salesperson : O(n!)

Conclusion

I really appreciate your efforts if you are still reading this article. Now, you must be thinking that, why time complexity is so important to understand? We know that for small number of elements (say 10) the difference between the number of operations performed by binary search and linear search is not so big, but in real world, most of the time we deal with the problems that have big chunks of data. For example if we have 4 billion elements to search for then, in its worst case, linear search will take 4 billion operations to complete its task whereas binary search will complete this task in just 32 operations. That’s a big difference. Now let’s assume that if one operation takes 1 ms for completion then binary search will take only 32 ms whereas linear search will take 4 billion ms that is 46 days (approx). That’s a huge difference. This is the reason why studying time complexity becomes important when it comes to such a big amount of data.

If you liked this article then please make sure to clap and if I was wrong about something or I missed something then please mention about that as well and finally Thanks a lot for your time.