December 26, 2012

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 N2. 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 N2. Thus these algorithms are expensive with respect to time performance. There are algorithms that have the time complexity proportional to N log2 (N). The following table shows the respective values of N2 and N log2(N) for some values of N.

N N2 N Log2 (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 N2 is very large as compared to the value of N log2 (N). Thus we see that the algorithms whose time complexity is proportional to N2 are much time consuming as compared to the algorithms the time complexity of which is proportional to N log2 (N). Thus we see that the N log2 (N) algorithms are better than the N2 algorithms.

N log2 (N) Algorithms
Now let’s see the algorithms that are N log2 (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.

  


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


clip_image002

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.

clip_image003

After this we merge these two parts and get the sorted array as shown below.

clip_image004







No comments:

Post a Comment

C program to Read From a File

#include <stdio.h> #include <stdlib.h> void main() {     FILE *fptr;     char filename[15];     char ch;   ...