Consider the following six functions:
For each of the following sets, indicate which of the above functions are members of the set:
For each of the recurrence equations below:
As an example, the recurrence equations for selection sort on an array of n elements would be:
T(n) = n + T(n  1), n > 0,
T(0) = 0
(Assume that finding the minimum of n elements takes n operations.) The closedform solution to the recurrence equation can be derived as follows:
T(n) = n + T(n1)
= n + (n  1) + T(n2)
= n + (n  1) + (n  2) + T(n3)
...
= n + (n 1) + (n  2) + (n  3) + ... + 3 + 2 + 1
= n(n+ 1)/2.This function is an element of Q(n^{2})
a.
T(n) = 3 + T(n  1), n > 0
T(0) = 0
b.
T(n) = 3n + T(n  1), n > 0
T(0) = 0
c.
T(n) = 1 + 3T(n  1), n > 0
T(0) = 0
d.
T(n) = 1 + T(n/3), n „ 1
T(n) = 0, n < 1
e.
T(n) = n + T(n/3), n „ 1
T(n) = 0, n < 1
Below are six class methods, all of which compute the value of 2 raised to the nth power. For each function, give the following:
a. A recurrence equation that approximates the worstcase running time T(n) of the routine as a function of the input n. In all cases, you may assume that T(n) = 0 for n < 1 and that the overhead of the divide and glue operations within the body of twoi has cost that is a constant (for convenience, assume that the constant is 1).
b. A solution to the recurrence equation expressed in Q notation.
You may find the following facts helpful in some of your analyses, especially for two6.
public static int two1 (int n) { if (n == 0) { return 1; } else { return 2 * two1(n  1); } } public static int two2 (int n) { if (n == 0) { return 1; } else { return two2(n  1) + two2(n  1); } } public static int two3 (int n) { if (n == 0) { return 1; } else { return two3(n  1) + two1(n  1); // Note call to two1. } } public static int two4 (int n) { // To simplify analysis, assume that the input to two4 is a power of 2. if (n == 0) { return 1; } else if (n % 2 == 0) { int x = two4(n / 2); return x * x; } else { return 2 * two4(n  1); } } public static int two5 (int n) { // To simplify analysis, assume that the input to two5 is a power of 2. if (n == 0) { return 1; } else if (n % 2 == 0) { two5(n / 2) * two5(n / 2) } else { return 2 * two5(n  1); } } public static int two6 (int n) { if (n == 0) { return 1; } else { return two6(n  1) + two4(n  1) // Note call to two4. } }
When working for AsSorted Systems as a summer intern, Bud Lojack (correctly) implemented four sorting algorithms for lists: selection sort, insertion sort, merge sort, and quick sort. But instead of giving meaningful names to his routines, Bud named them sort1, sort2, sort3, and sort4. When writing up a report at the end of the summer, Bud needs to figure out which routine corresponds to which algorithm. Unfortunately, Bud has accidentally deleted the source files for his routines and can't even inspect the code to determine which routine implements which algorithm. The only the thing he can do is test the routines on various inputs. Below are his timing results for running the routines on input lists of varous sizes. (All times are reported in milliseconds.) For each routine, he has tested the routine on both already sorted lists and on randomly ordered lists.
Time for sort1 to sort sorted list with 400 elements: 4 Time for sort1 to sort sorted list with 800 elements: 8 Time for sort1 to sort sorted list with 1600 elements: 16 Time for sort1 to sort sorted list with 3200 elements: 26 Time for sort1 to sort random list with 400 elements: 255 Time for sort1 to sort random list with 800 elements: 958 Time for sort1 to sort random list with 1600 elements: 4059 Time for sort1 to sort random list with 3200 elements: 16585 Time for sort2 to sort sorted list with 400 elements: 92 Time for sort2 to sort sorted list with 800 elements: 339 Time for sort2 to sort sorted list with 1600 elements: 1356 Time for sort2 to sort sorted list with 3200 elements: 5321 Time for sort2 to sort random list with 400 elements: 13 Time for sort2 to sort random list with 800 elements: 37 Time for sort2 to sort random list with 1600 elements: 71 Time for sort2 to sort random list with 3200 elements: 143 Time for sort3 to sort sorted list with 400 elements: 229 Time for sort3 to sort sorted list with 800 elements: 907 Time for sort3 to sort sorted list with 1600 elements: 3311 Time for sort3 to sort sorted list with 3200 elements: 13634 Time for sort3 to sort random list with 400 elements: 205 Time for sort3 to sort random list with 800 elements: 890 Time for sort3 to sort random list with 1600 elements: 3318 Time for sort3 to sort random list with 3200 elements: 13689 Time for sort4 to sort sorted list with 400 elements: 23 Time for sort4 to sort sorted list with 800 elements: 37 Time for sort4 to sort sorted list with 1600 elements: 87 Time for sort4 to sort sorted list with 3200 elements: 178 Time for sort4 to sort random list with 400 elements: 24 Time for sort4 to sort random list with 800 elements: 51 Time for sort4 to sort random list with 1600 elements: 102 Time for sort4 to sort random list with 3200 elements: 213
Part a. Based on Bud's data, fill in the following table with the asymptotic notation that best describes the running time of the routine on a particular type of list. You should use one of the following for every entry of the table: Q(1), Q(log(n)), Q(n), Q(nlog(n)), Q(n^{2}), Q(n^{3}). (Note: because the numbers are taken from an actual implementation, they may not fit any category exactly; if the category is ambiguous, say so!)



sort1 


sort2 


sort3 


sort4 


Part b. Based on the table from part a, determine for each of Bud's four routines which of the four sorting algorithms it uses. Briefly explain your reasoning.
Part c. Answer the following for the four sorting algorithms that Bud has implemented:
i. Which sorting algorithm(s) does much better on sorted lists than on randomly ordered lists. Why?
ii. Which sorting algorithm(s) does much worse on sorted lists than on randomly ordered lists. Why?
iii. Which sorting algorithm(s) takes about the same amount of time on both sorted and randomly ordered lists. Why?