Due Date: Friday, March 1, 2013, 23:59:59
Weight: 4%

You will submit your solution to this assignment to the Curator System (as HW2). Your solution must be either a plain text file or a PDF document; submissions in other formats will not be graded.
Except as noted, credit will only be given if you show relevant work.

1. Time Analysis

[30 points] Using the rules given in the course notes, perform an exact count complexity analysis, for the worst case, of the body of the following function. (Take the cost of list.length to be 2.)

public void duplex(int[] list) { int maxIdx, min, max, small, large; maxIdx = list.length - 1; small = list[0]; min = 0; large = list[maxIdx]; max = maxIdx; for (int minmax = 0; minmax <= maxIdx; minmax++) { if (list [ minmax ] < small) { min = minmax; small = ray [ minmax ]; } else if (list [ minmax ] > large) { max = minmax; large = ray [ minmax ]; } } if ( (max == 0) && (min == maxIdx) ) { swap( list, 0, maxIdx ); } else if (max == 0) { swap( list, max, maxIdx ); swap( list, 0, min ); } else { swap( list, min, 0 ); swap( list, max, maxIdx ); } } public void swap(int[] list, idxA, idxB) { int tmp = list[idxA]; list[idxA] = list[idxB]; list[idxB] = tmp; }

2. Growth: input

[20 points] Problem 2.11 from the textbook.

An algorithm takes 0.5 ms for input size 100. How long will it take for input size 500 if the running time is the following (assume low-order terms are negilible).

1. linear
2. O( N log N )
3. quadratic
4. cubic