Time Complexity | Algorithms - Computer Science Engineering (CSE) PDF Download

Introduction

We might have come across various instances where we need to process the data in a specific format without taking any further delay and the same in case of unsorted data processed with higher speed so that results could be put to some use. In such instances, we use sorting algorithms so that the desired efficiency is achieved. In this article, we will discuss various types of sorting algorithms with higher emphasis on time complexities. But, before moving any further, let's understand what complexity is and what's so important to talk about it.

Complexity

Complexity has no formal definition at all. It just defines the rate of efficiency at which a task is executed. In data structures and algorithms, there are two types of complexities that determine the efficiency of an algorithm. They are:

• Space Complexity: Space complexity is the total memory consumed by the program for its execution.
• Time Complexity: It is defined as the times in number instruction, in particular, is expected to execute rather than the total time is taken. Since time is a dependent phenomenon, time complexity may vary on some external factors like processor speed, the compiler used, etc.

In computer science, the time complexity of an algorithm is expressed in big O notation. Let's discuss some time complexities.

• O(1): This denotes the constant time. 0(1) usually means that an algorithm will have constant time regardless of the input size. Hash Maps are perfect examples of constant time.
• O(log n): This denotes logarithmic time. O(log n) means to decrease with each instance for the operations. Binary search trees are the best examples of logarithmic time.
• O(n): This denotes linear time. O(n) means that the performance is directly proportional to the input size. In simple terms, the number of inputs and the time taken to execute those inputs will be proportional or the same. Linear search in arrays is the best example of linear time complexity.
• O(n2): This denotes quadratic time. O(n2) means that the performance is directly proportional to the square of the input taken. In simple, the time taken for execution will take square times the input size. Nested loops are perfect examples of quadratic time complexity.

Let's move on to the main plan and discuss the time complexities of different sorting algorithms.

Time Complexity of Bubble Sort

Bubble sort is a simple sorting algorithm where the elements are sorted by comparing each pair of elements and switching them if an element doesn't follow the desired order of sorting. This process keeps repeating until the required order of an element is reached.

• Average case time complexity: O(n2)
• Worst-case time complexity: O(n2)
• Best case time complexity: O(n)

The best case is when the given list of elements is already found sorted. This is why bubble sort is not considered good enough when the input size is quite large.

Time Complexity of Selection Sort

Selection sort works on the fundamental of in-place comparison. In this algorithm, we mainly pick up an element and move on to its correct position. This process is carried out as long as all of them are sorted in the desired order.

• Average case time complexity: O(n2)
• Worst-case time complexity: O(n2)
• Best case time complexity: O(n2)

Selection sort also suffers the same disadvantage as we saw in the bubble sort. It is inefficient to sort large data sets. It is usually preferred because of its simplicity and performance-enhancing in situations where auxiliary memory is limited.

Time Complexity of Insertion Sort

Insertion sort works on the phenomenon by taking inputs and placing them in the correct order or location. Thus, it is based on iterating over the existing elements while taking input and placing them where they are ought to be.

• Best case time complexity: O(n)
• Average and worst-case time complexity: O(n2)

• Best and Average time complexity: O(n log n)
• Worst-case time complexity: (n2)

Time Complexity Of Merge Sort

Merge Sort also works under the influence of the divide and conquer algorithm. In this sorting technique, the input array is divided into half, and then these halves are sorted. After sorting, these two halved sub-arrays are merged into one to form a complete sorted array.

• Best and Average time complexity: O(n log n)
• Worst-case time complexity: O(n log n)

Conclusion

Time complexity plays a crucial role in determining the overall performance of a program. It is solely intended to improve the performance of a program and impact the overall performance of the system. However, with great speed comes greater responsibility. Hence, to achieve the best time complexity, a developer needs to have a keen eye on using a particular algorithm or technique that delivers the best case complexity. Furthermore, to be at such a pace, a developer needs to carry prior knowledge about the sorting algorithm. Therefore, it is highly recommended to understand each of the techniques discussed in this article in detail and figure out the best one that suits the situation.