Solutions to the Practice Questions

Solutions to the Practice Questions#

Order Notation#

b, c, d, e, g (not a or f)
a, b, d, e, f (not c or g)
only d

An Example of Different Complexity Classes#

Finding the maximum:

/**
 * Returns the maximum integer in aList.
 * @param aList 1d array of integers
 * @return the maximum integer in aList.  If aList is empty this
 *         will throw an exception.
 */
 public static int findMax(int[] aList){
    int max = aList[0];
    for (int i = 0; i < aList.length; i++){
       if (aList[i] > max){
          max = aList[i];
       }
    }
    return max;
 }//findMax

If aList is of size \(n\) elements, the worst number of key comparisons is \(n\) (look at everything once). This means that the run-time of findMax is in \(θ(n)\).

Finding the maximum in a sorted list, ascending order:

public static int findMax(int[] aList){
   return aList[aList.length - 1];
}

The run-time of this algorithm is constant, i.e. in \(θ(1)\).
We can’t do better than constant time. Less than constant time would be zero time or negative time, but that means we are not running anything or going backwards in time.

Back to Questions

The Seven Most Common Computing Efficiency Functions#

a. Could figure this out by trying various values of n, e.g. 10, 11, 12, 13, 14.
Exact complexity is:

\[\begin{split} C(n)= \left\{ \begin{array}{ll} n(\frac{n}{2}) & n \text{ is even}\\ \frac{n(n+1)}{2} & n \text{ is odd} \\ \end{array} \right. = n \lfloor \frac{n+1}{2} \rfloor \end{split}\]

b. Order notation: \(θ(n^2)\)
a. Try various values of n to figure this out, e.g. n = 24, 25, 26, 124, 125, 126, 624, 625, 626.
Exact complexity is: \(⌊\log _5 ⁡n ⌋+1+1= ⌊\log _5⁡ n ⌋+2\)
b. Order notation: \(θ(\log ⁡n)\)
a. There are exactly two assignments to answer, each time, since \(\frac{5}{n}\) is 0 for all \(n > 10\).
Exact complexity is: 2
b. Order notation: θ(1)

Start:        [89, 12, 56, 24, 69]
After pass 1: [12, 89, 56, 24, 69]
After pass 2: [12, 24, 89, 56, 69]
After pass 3: [12, 24, 56, 89, 69]
After pass 4: [12, 24, 56, 69, 89]

Start:        [10, 18, 21]
After pass 1: [10, 18, 21]
After pass 2: [10, 18, 21]

Size 10: 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45
Size n: The first time through the inner loop, it executes n-1 times, therefore doing n-1 key comparisons. The 2nd time it executes n-2 times, etc., until it ends with 1 key comparison. This leads to the summation:

\[ \sum \limits_{i=1}^{n-1} i = \frac{(n-1)n}{2} = \frac{n^2 - n}{2} \]

One way to do this:

/**
 * Returns true if the list contains a duplicate; false otherwise.
 * @param list - 1d array of integers
 * @return true if duplicate; false if unique
 */
public static boolean hasDuplicate(int[] list){
   int current;
   for (int i = 0; i < list.length - 1; i++){
      current = list[i];
      for (int j = i + 1; j < list.length; j++){
         if (current == list[j]){
            return true;
         }//if
      }//for
   }//for
   return false;
}//hasDuplicate

Worst-case occurs when there are no duplicates. The complexity is the same as for bubble sort (see question 6), which is \(\frac{(n-1)(n)}{2}\) key comparisons. This algorithms runs in \(θ(n^2)\).

public static void selectionSort(int[] list){
   int len = list.length; //In Java, the length is available; no param required
   int counter = 0;
   int otherCount;
   int min;
   int minIndex;
 
   while (counter < len - 1){
      min = list[counter];
      minIndex = counter;
      otherCount = counter + 1;
     
      while (otherCount < len){
         if (list[otherCount] < min){ //new min found
            min = list[otherCount];
            minIndex = otherCount;
         }
         otherCount++;
      }
     
      // Exchange
      list[minIndex] = list[counter];
      list[counter] = min;
     
      counter++;
   }
}

Original: {98, 12, 32,  3,  7, 19, 54, 87}
Pass 1:   { 3, 12, 32, 98,  7, 19, 54, 87}
Pass 2:   { 3,  7, 32, 98, 12, 19, 54, 87}
Pass 3:   { 3,  7, 12, 98, 32, 19, 54, 87}
Pass 4:   { 3,  7, 12, 19, 32, 98, 54, 87}
Pass 5:   { 3,  7, 12, 19, 32, 98, 54, 87}
Pass 6:   { 3,  7, 12, 19, 32, 54, 98, 87}
Pass 7:   { 3,  7, 23, 19, 32, 54, 87, 98}

In \(\theta (n^2)\)

public static void insertionSort(int[] list){
   int len = list.length;
   int counter = 1;
   int newElement;
   int location;

   while (counter < len){
      newElement = list[counter];
      location = counter - 1;
    
       while (location >= 0 && list[location] > newElement){
          list[location + 1] = list[location];
          location--;
       }
    
       list[location + 1] = newElement;
       counter++;
   }
}

Original: {98, 12, 32,  3,  7, 19, 54, 87}
Pass 1:   {12, 98, 32,  3,  7, 19, 54, 87}
Pass 2:   {12, 32, 98,  3,  7, 19, 54, 87}
Pass 3:   { 3, 12, 32, 98,  7, 19, 54, 87}
Pass 4:   { 3,  7, 12, 32, 98, 19, 54, 87}
Pass 5:   { 3,  7, 12, 19, 32, 98, 54, 87}
Pass 6:   { 3,  7, 12, 19, 32, 54, 98, 87}
Pass 7:   { 3,  7, 12, 19, 32, 54, 97, 98}

In \(\theta (n^2)\)