Introduction to Algorithms 3rd Edition - Exercises 2.2-1 to 2.2-4

2.2-1
Express the function n3=1000 100n2 100n C 3 in terms of ‚-notation.

theta(n3)

2.2-2
Consider sorting n numbers stored in array A by first finding the smallest element
of A and exchanging it with the element in AOE1 . Then find the second smallest
element of A, and exchange it with AOE2 . Continue in this manner for the first n 1
elements of A. Write pseudocode for this algorithm, which is known as selection
sort. What loop invariant does this algorithm maintain? Why does it need to run
for only the first n 1 elements, rather than for all n elements? Give the best-case
and worst-case running times of selection sort in ‚-notation.

/ *
 * Best Average Worst Memory Stable
 * N ^ 2 n ^ 2 n ^ 2 1 No (5,8,5,1,9)
* / 
Public  Class SelectionSort {

    Public  static  void Sort ( int [] a) {
         for ( int i = 0; i <a.length-1; i + + ) {
             int Key = a [i];
             int index = i;
             for ( int i = J +1 ; J <a.length; J + + ) {
                 if (a [J] < Key) {
                    Key = a [J];
                    index = J;
                }
            }
            a [index] = a [i];
            a [i] = Key;
        }
    }
    
    Public  static  void printArray ( int [] a) {
         for ( int i = 0; i <a.length; i + + ) {
            System.out.print (a [i] + "" );
        }
    }
    
    Public  static  void main (String [] args) {
          int [] a = {2, 0, 1,5,5, 4, 9, 8, 6, 7, 10, 3 };
         sort (a);
         printArray (a);
    }

}

Worst Case: theta(n^2) 

Best Case: theta(n)

2.2-3


Consider linear search again (see Exercise 2.1-3). How many elements of the input
sequence need to be checked on the average, assuming that the element being
searched for is equally likely to be any element in the array? How about in the
worst case? What are the average-case and worst-case running times of linear
search in ‚-notation? Justify your answers.


theta(n)