Fall 2012

HW3: Algorithm Analysis

- Answer the following questions from Shaffer, section 3.13 (pp. 85-88): 3.3, 3.5, 3.8, 3.12

- Write a short program to verify experimentally that the
`Collections.sort`

method is indeed O(N log N). Your program should generate an ArrayList of random numbers (whose size is specified by the user). It should then sort the list using the`Collections.sort`

method and time the sort. Note: one way to estimate run-time is to utilize the`System.currentTimeMillis`

method. For example:long startTime = System.currentTimeMillis(); // CODE TO BE TIMED long endTime = System.currentTimeMillis(); long duration = endTime - startTime; Provide run-times for your code on increasingly large lists of numbers, and argue whether your data supports the claim that

`Collections.sort`

is O(N log N).