CSC 321: Data Structures
Fall 2012

HW3: Algorithm Analysis

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

  2. 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).