CmSc 250 Fundamentals of Computing III
Homework 05 SOLUTION
1. Determine the running time of mergesort for
a. Sorted input
b. Reverse-ordered input
c. Equal elements
Explain your answers.
In the three cases the running time is O(NlogN). It is computed based on the recurrence relation derived from the recursive part of the algorithm:
mergesort(A, left, right)
{ if (left = right) return;
else
mergesort(A, left, mid)
mergesort(A, mid, right)
merge(A, left, mid, right)
}
The recurrence relation is: T(N) = 2T(N/2) + N
Since merging requires the same operations for sorted or equal elements.
Solving the recurrence relation results in O(NlogN)
2. Using the median-of-three partitioning, determine the running time of quicksort for
a. Sorted input
b. Reverse-ordered input
c. Equal elements
Explain your answers.
In the three cases the pivot will be the middle element in the array, and thus we have the best case of O(NlogN) run time. However there will be a slight difference due to the different number of swappings to form the partitions.
In case a) there will be practically no swappings, since the elements are in correct order with respect to the pivot. In case b) the first step will require swapping all elements, and after that they will be in correct order, so the next steps will not require swappings. In case c) all recursive steps will require swappings, since the algorithm compares by “<” and “>”, not by “=”.
3. Repeat exercise 2 when the pivot is chosen as
a. The first element
b. The larger of the first two elements
c. Random element
Explain your answers.
a) if the array is sorted (no matter whether in the right or reversed order) choosing the first element as a pivot will result in one of the partitions to be empty, so we have the worst case O(n2). With equal elements it does not matter how we choose the pivot, hence the run time will be O(NlogN).
b) Choosing the larger of the first two elements will not improve significantly the situation – instead of an empty partition we will have a partition of one element, so again for sorted arrays the run time will be O(n2), and for equal elements it does not make any difference, so we will have O(NlogN).
c) Choosing a random pivot will not change the situation with equal elements – O(NlogN). With sorted elements we may have the worst case O(n2) if the pivot happens to be the smallest or the largest element, or the best case of O(NlogN) if the pivot happens to be close to the middle element. On average it has been proved that the run time is expected to be O(NlogN).
4. Suppose we choose the element in the middle position of the array as pivot. Does this make it unlikely that quicksort will require quadratic time? Explain your answer.
Choosing the pivot to be the middle (by position) element does not guarantee that it will not be the smallest or the largest element. So we still may have O(n2) run time.
5. We are given an array that contains N numbers. We want to determine if there are two numbers whose sum equals a given number K. For example, if the input is 8, 4, 1, 6, and K is 10. then the answer is yes (4 and 6). A number may be used twice if it is repeated in the input.
a. Give an O(N2) algorithm (pseudocode or actual code) to solve this problem.
found = false;
for (i = 0; i < N-1 & !found; i++)
for (j = i+1, j < N & !found; j++)
if (array[i] + array[j] == K) found = true
if (found) print “Yes”
else print “No”
b. Give an O(NlogN) algorithm (pseudocode or actual code) to solve this problem.
Step 1: Sort the array (O(NlogN))
Step 2:
for (j = 0; j < N; j++)
perform binary search for (K – array[j]) (O(logN)
if found print Yes, stop
if no search is successful, print No
The for loop runs N times at most and the body has O(logN) run time, so this algorithm has O(NlogN) complexity.
6. Compute the first six terms of the sequence defined by each of the recurrence relations and initial conditions that follow:
a. an = an -1 + 2 an-2 , a0 = 1, a1 = 5
1, 5, 7, 17, 31, 65
b. an = 6an -1 - 9 an-2 , a0 = 2, a1 = 7
2, 7, 24, 81, 270, 891
c. an = an -1 + 3n + 4 , a0 = 2
2, 9, 19, 32, 48, 67
7. Obtain a recurrence relation for each of the following:
a. The series 1 + 4 + 9 + …. + n2
A1 = 1
An = n2
A n+1 = (n+1)2 = n2 +2n + 1 = An + 2n + 1
b. The sequence 3, 9, 81, …
A1 = 3
A n+1 = (An)2
c. The sequence a, ra + d, r(ra + d) + d, r(r(ra + d) + d ) + d,…
A1 = a
A n+1 = r(An ) + d
3