2.2 Analyzing algorithms

2.2-1

Θ(n3).

2.2-2

Pseudocode:

SELECTION-SORT (A)

1 for i = 1 to A.length - 1
2     min_index = i
3
4     for j = i + 1 to A.length
5         if A[min_index] > A[j]
6             min_index = j
7
8     if i != min_index:
9         temp = A[i]
10        A[i] = A[min_index]
11        A[min_index] = temp

Loop invariant:

At the start of each iteration of the outer for loop, the subarray A[1..i - 1] consists of elements that are in sorted order.

Why does it need to run for only the first n - 1 elements, rather than for all n elements?

When i equals to A.length - 1, only the last two elements may not be in sorted order, and we need to find the A.length - 1 smallest element, so we compare A[A.length - 1] and A[A.length]. We put the smaller element at the index of A.length - 1, and put the larger element at the index of A.length. So after this iteration, the last element of the array is already the largest number. So it's not necessary to run for the nth element.

Give the best-case and worst-case running times of selection sort in Θ notation.

Let's first see the cost of each statement and the number of times each statement is executed. We let ti denote the number of times the operation in line 6 is executed for that value of i, and let pi denote the number of times the operation in line 9/10/11 is executed for that value of i.

Line number Cost Times
1 c1 n
2 c2 n1
4 c4 i=1n1(ni+1)=n(n+1)21
5 c5 i=1n1(ni)=n(n1)2
6 c6 i=1n1ti
8 c8 n1
9 c9 i=1n1pi
10 c10 i=1n1pi
11 c11 i=1n1pi

So the running time of selection sort is:

T(n)=c1n+c2(n1)+c4(n(n+1)21)+c5n(n1)2+c6i=1n1ti+c8(n1)+ (c9+c10+c11)i=1n1pi

Now let's see the best-case. The best-case occurs if the array is already sorted. Thus ti and pi are both 0, and the best-case running time is:

T(n)=c1n+c2(n1)+c4(n(n+1)21)+c5n(n1)2+c8(n1) =(c42+c52)n2+(c1+c2+c42c52+c8)n(c2+c4+c8) =Θ(n2)

And the worst-case occurs if the array is in reverse sorted order. Thus in the iteration of j, line 6 is executed from i + 1 to A.length - (i - 1) (because after the first iteration of i, the largest element is at the index of A.length, after the second iteration of i, the second largest element is at the index of A.length - 1, so the last i - 1 elements are bigger than the previous elements), so ti=ni(i1)=n2i+1. So the times of line 6 is c6i=1n1(n2i+1), notice that n2i+1 will be 0, when it's 0, it's not necessary to sum it, to make it simple, let's assume it stops when i=n2. So:

i=1n1(n2i+1)=(n1)+(n3)++1 =nn2(1+3+5++(2n21)) =n22n2(1+n1)2 =n24

Now let's see pi, we already assume that line 6 will not be executed when in2, which also means line 9 to line 11 will not be executed. So i=1n1pi should be n2. So the running time of worst-case is:

T(n)=c1n+c2(n1)+c4(n(n+1)21)+c5n(n1)2+c6n24+c8(n1)+c9+c10+c112n =(c42+c52+c64)n2+(c1+c2+c42c52+c8+c9+c10+c112)n(c2+c4+c8) =Θ(n2)

2.2-3

How many elements of the input sequence need to be checked on the average?

Since the element being searched for is equally likely to be any element in the array, so the probability of finding the target value at index i is 1/n, and it will check i elements. So the average checks is:

1n(1+2+3++n1+n)=1nn(n+1)2=n+12

And the worst case will check n elements. The running time of average case and worst case are both Θ(n).

2.2-4

We can check if the input is a best-case first, if it is true, then we can return a predefined solution for that best-case. For example, in a sorting algorithm, if the input is sorted, then we can return the array directly.