Page 563 - Computer science 868 Class 12
P. 563

If the number to be searched is not present in the array, then the loop executes n times. Thus, the worst case complexity
                 of linear search is O(N).
                 If the number to be searched is present in any other position, then the numbers of steps executed is greater than O(1)
                 and less than O(N) which is the average case complexity.


                     14.5 ANALYSIS OF COMPLEXITY OF COMMON ALGORITHMS
                 Bubble Sort: The algorithm for bubble sort is given below.
                    for(int i=0;i<n-1;i++)
                        { for(int j=0;j<n-i-1;j++)
                          { if(a[j]>a[j+1])
                            { int t=a[j];
                              a[j]=a[j+1];
                              a[j+1]=t;
                            }
                        }
                 The worst case complexity for an array of size n will be as follows:
                    st
                 In 1  pass through j loop: n-1 comparisons and n-1 swaps take place
                    nd
                 In 2  pass: n-2 comparisons and n-2 swaps take place
                                th
                 Similarly, in (n-1)  pass through j loop: one comparison and one swap take place.
                 All together: c ((n-1) + (n-2) + ... + 1)

                 [where c = time for one comparison + one swap + check j loop condition + increment j and i loop is executed n-1 times]
                 if c1= time required to check loop condition + incrementing

                 Then total time:
                 c ((n-1) + (n-2) + ... + 1) + c1 (n-1)

                 = n(n-1)/2 + c1(n-1)
                 = c(n -n)/2+c1(n-1)
                     2
                                                                  2
                 Here, n  is the dominant term. Hence, complexity is Ọ(n ).
                       2
                 If bubble sort is performed on a list that is already sorted, it will finish in O(n) time which is its best case complexity.
                 The average and worst case complexity of a Bubble Sort algorithm is O(N ).
                                                                                 2
                 Selection Sort: The algorithm for selection sort is given below.

                    for(int i=0;i<size-1;i++)
                        { s=a[i];
                          p=i;
                          for(int j=i+1;j<size;j++)
                          { if(s<a[j])
                            { s=a[j];
                              p=j;
                            }
                         }
                         t=a[i];
                         a[i]=a[p];
                         a[p]=t;
                      }

                                                                                                                       561
                                                                              Computational Complexity and Big O Notation  561
   558   559   560   561   562   563   564   565   566   567   568