Exercise 2.2

Exercise 2.2-1¶

Express the function $n^3/1000 - 100n^2 - 100n + 3$ in terms of $\Theta$-notation

Exercise 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 A[1]. Then find the second smallest element of A, and exchange it with A[2]. 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 $\Theta$-notation.

Pseudocode

SELECTION-SORT(A)

1  for i = 1 to n - 1
2     min = i
3     for j = i + 1 to n
4         if A[j] < min
5             min = A[j]
6     swap(A[min], A[i])

Loop Invariant: At each iteration i, subarray A[1..i-1] is in sorted order.

The algorithm need to run only for the first n - 1 elements because, after completing n - 1 iterations, the subarray A[1..n-1] contains the first n - 1 smallest elements of the array A. Hence the last element A[n] is always the maximum element which is already in the right place.

For selection sort, the best case and worst case running time are $\Theta(n^2)$. This is because, both the outer and inner loops are executed regardless of the elements.

Python code

def selection_sort(A):
    """Sorts the array `A` in ascending order using `Selection sort` algorithm

    Args:
        A: Array of numbers to be sorted

    Returns:
        Array of numbers in sorted, ascending order
    """
    for i in range(0, len(A) - 1):
        min_index = i
        for j in range(i + 1, len(A)):
            if A[j] < A[min_index]:
                min_index = j
        A[min_index], A[i] = A[i], A[min_index]  # Swap
    return A

tests = [
    [31, 41, 59, 26, 41, 58],
    [],
    [40, 20],
    [1],
    [10, 9, 8, 7],
    [7, 8, 9, 10]
]

for input_array in tests:
    print(f'Input: {input_array}')
    output_array = selection_sort(input_array)
    print(f'Sorted: {output_array}\n')

Input: [31, 41, 59, 26, 41, 58]
Sorted: [26, 31, 41, 41, 58, 59]

Input: []
Sorted: []

Input: [40, 20]
Sorted: [20, 40]

Input: [1]
Sorted: [1]

Input: [10, 9, 8, 7]
Sorted: [7, 8, 9, 10]

Input: [7, 8, 9, 10]
Sorted: [7, 8, 9, 10]

Exercise 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 $\Theta$-notation? Justify your answers.

For simplicity assume that, average case means the element is found midway.

If there are n elements in the array A, then on an average n/2 elements need to be checked. If the value we are looking for is not present in the array, we would have to scan the entire array. Hence worst case, we need to check all the n elements.

Let us calculate the running time of Linear search

   LINE                      cost   times
1  i = NIL                    c1      1
2  for j = 1 to A.length      c2     n+1
3      if A[j] = v            c3      n
4          i = j              c4      1 or 0 
5          return i           c5      1 or 0
6  return i                   c6      1

For worst case,

For average case

Exercise 2.2-4¶

How can we modify almost any algorithm to have a good best-case running time?

To achieve good best-case running time, predefine or generate an output before running the actual steps. Check if the output satisfies the goal or termination invariant. For example, in Insertion sort, predefine output same as input. In best case, it would already be in sorted order.