Easy Learning: Comparison of Complexity of Algorithms

We have studied these three algorithms i.e. selection sort, insertion sort and bubble sort. Now considering the above three algorithms, we see that these algorithms are easy to understand. Coding for these algorithms is also easy. These three algorithms are in place algorithms. There is no need of extra storage for sorting an array by these algorithms. With respect to the time complexity, these algorithms are proportional to N². Here N is the number of elements. So we can see that as the value of N increases, the performance time of these algorithms increases considerably as it is proportional to N². Thus these algorithms are expensive with respect to time performance. There are algorithms that have the time complexity proportional to N log₂ (N). The following table shows the respective values of N² and N log₂(N) for some values of N.

N	N²	N Log₂ (N)
10	100	33.21
100	10000	664.38
1000	1000000	9965.78
10000	100000000	132877.12
100000	10000000000	1660964.04
1000000	1E+12	19931568.57

From this table we can see that for a particular value of N, the value of N² is very large as compared to the value of N log₂ (N). Thus we see that the algorithms whose time complexity is proportional to N² are much time consuming as compared to the algorithms the time complexity of which is proportional to N log₂ (N). Thus we see that the N log₂ (N) algorithms are better than the N² algorithms.

N log₂ (N) Algorithms

Now let’s see the algorithms that are N log₂ (N) algorithms. These include the following algorithms.

Merge Sort
Quick Sort
Heap Sort

These three algorithms fall under ‘divide and conquer category’. The divide and conquer strategy is well known in wars. The philosophy of this strategy is ,’ divide your enemy into parts and then conquer these parts’. To conquer these parts is easy, as these parts cannot resist or react like a big united enemy. The same philosophy is applied in the above algorithms. To understand the divide and conquer strategy in sorting algorithm, let’s consider an example. Suppose we have an unsorted array of numbers is given below.

Now we split this array into two parts shown in the following figure.

Now we have two parts of the array. We sort these parts separately. Suppose we sort these parts with an elementary sort algorithm. These parts may be sorted in the following manner.