Section 5.3 : Appilcations to the Analysis of Algorithms

Selection Sort :

This algorithm sorts the sequence s₁, s₂, ....,s_n in increasing order by first selecting the largest item and placing it last and then recursively sorting the remaining elements .

Input  :  s1, s2, ....,sn and the length n of the sequence 
Output :  s1, s2, ....,sn , arranged in increasing order


1.  procedure selection_sort(s,n) 
2. // base case
3.   if n = 1 then  
4.       return  
5.   // find largest
6.    max_index := 1   // assume initially that s1 is largest
7.    for i := 2 to n  do 
8.       if si >  smax_index then // find larger, and update
9.             max_index = i 
10.        // largest to end
11.     swap(sn, smax_index)
12.   call selection_sort(s, n-1) 
13.   end selection_sort


      Let b(n)  be the number of comparisons (line 8) required to sort n items.

       Then we have the following recurrence relation :

           b(1)  = 0  
   and     b(n) = b(n-1) + (n-1)

  To solve this recurrence relation, we use the iteration method :
 
         b(n) = b(n-1) + (n-1)  
              = b(n-2) + (n-2) + (n-1)
              = b(n-3) + (n-3) + (n-2) + (n-1)
                 .....
              = 0 + 1 + 2 + .... + (n-2) + (n-1)
              = n(n-1)/2   
              = Q(n2)

Binary Search

Input:    A sequence si,si+1,...., sj,  i >= 1, sorted in increasing order, 
          a value key , i and j 
Output :  The output is an index k for which sk = key, or if key is not in the
          sequence, the output is 0 



1.   procedure binary_search(s,i,j,key)
2.      if  i > j then    // not found
3.          return 0
4.      k := [(i+j)/2]   // integer division
5.      if key  = sk then  // found !!
6.         return  k
7.      if key < sk then    // search left half
8.          j := k - 1 
9.      else                           // search right half
10.           i := k + 1
11.    return binary_search(s,i,j,key)
12.  end binary_search



Let an be the number of comparisons for the worst case,
   then we have
                     an = a[n/2] + 1 
            with     a1 =  2

   We can solve this recurrence relation for n = 2k which reduces to

            bk = bk-1 + 1 

     with  b0 = 2 


                  bk = bk-1 + 1 
                     = bk-2 + 1 + 1
                     = bk-3 + 1 + 1 + 1
                      ....
                     = bk-j + j
                     = ....
                     = b0 + k
                     = k + 2
                     = lg n + 2
                     = Q(lg n)
                     



   For any arbitrary n, there is always an k such that

       2k-1 < n £  2k 

   and  k - 1 < lg n £ k

   Since the sequence a is increasing, we have the following :

             a2k-1 £ an £ a2k 

which will lead to :

  lg n < k + 1 £ an £ k + 2 < lg n + 3 = O(lg n)

Hence an = Q(lg n ) .