• Bailey: Section 4.1 (Asymptotic Analysis Tools) and Chapter 5 (Sorting)

---

Problem 1: Asymptotic Notation

Consider the following six functions:

1. a(n) = 2n·log₂(n) + n + 5
2. b(n) = 3n² + 7n + 4
3. c(n) = 17
4. d(n) = 2ⁿ + 1
5. e(n) = log₃(n)
6. f(n) = 3n -2

For each of the following sets, indicate which of the above functions are members of the set:

1. O(n)
2. Q(n²)
3. W(log₂(n))
4. O(n² + 5n + 2)
5. W(3ⁿ)

---

Problem 2: Recurrence Equations

For each of the recurrence equations below:

1. Give an exact closed form solution to the equations
2. Classify the solution to the equations using Q notation.

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 closed-form solution to the recurrence equation can be derived as follows:

T(n) = n + T(n-1)
= n + (n - 1) + T(n-2)
= n + (n - 1) + (n - 2) + T(n-3)
...
= n + (n -1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1
= n(n+ 1)/2.

This function is an element of Q(n²)

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

---

Problem 3: Running Time Analysis

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 worst-case 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.

• log₂(a) + log₂(b) = log₂(a*b)
• log₂(a) - log₂(b) = log₂(a/b)
• n! = n*(n-1)*(n-2)*... 3*2*1
• log₂(n!) is an element of Q(n*log₂(n))
• if f is an element of O(g) but f is not an element of Q(g), then Q(f + g) = Q(g)

  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.
    }
  }

---

Problem 4 : Identifying Sorting Algorithms

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²), Q(n³). (Note: because the numbers are taken from an actual implementation, they may not fit any category exactly; if the category is ambiguous, say so!)

	Sorted List	Unsorted List
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?