Page 564 - Computer science 868 Class 12
P. 564

The complexity calculation is some what similar to Bubble Sort.
              In the first pass, j loop executes (n-1) times.

              In the second pass, j loop executes (n-2) times.

              In this way, the j loop executes 1 time in the last pass.
              Thus, total number of steps executed is

               (n-1)+(n-2)+(n-3).......+2+1
              = n(n-1)/2

                 2
              = n /2 - n/2
                                       2
                                                                                          2
              The dominant term being N  is considered. So, the complexity of Selection Sort is O(N ).
              Insertion Sort: The algorithm for insertion sort is given below.

                  for (int i = 1; i < n; ++i)
                          {
                              int key = a[i];
                              int j = i - 1;
                              while (j >= 0 && a[j] > key) {
                                  a[j + 1] = a[j];
                                  j = j - 1;
                              }
                              a[j + 1] = key;
                          }
                      }
              Total number of times the loop executed is: 1+2+3+....+(n-1)
              = n*(n-1)/2

              = n /2 - n/2
                 2
                                                                                          2
                                       2
              The dominant term being N  is considered. So, the complexity of Insertion Sort is O(N ).
              The best case complexity where the data is already sorted is O(N).

              The worst and average case complexity is O(N ).
                                                       2




                              Let’s Revisit


                    ♦ The effectiveness of an algorithm is depicted by how accurately it produces a result.
                    ♦ An efficient algorithm is one which produces accurate result in minimum time using minimum resources.
                    ♦ Computation involves the process of solving a problem and the algorithm associated with it. Complexity involves the study of
                   factors like time taken by an algorithm and space utilised by it to determine the minimum resource requirement. Complexity
                   is thus the measurement of the performance of an algorithm.
                    ♦ Space complexity is the amount of memory space required to run an algorithm. An algorithm which requires the least memory
                   is considered more efficient.
                    ♦ Time complexity is the total time taken to execute the instructions (steps) of a program. An algorithm which is designed using
                   the least number of steps is considered more efficient.




                562562  Touchpad Computer Science-XII
   559   560   561   562   563   564   565   566   567   568   569