Computer Science 15-111 (Sections A & B), Spring 2007

Class (Recitation) Notes: 05-Mar-2007

Logistics:

1. No homework over Spring Break!

2. But… Quiz 5 is coming! Topics:

a. Complexity and Big-Oh

b. Packages

c. Quicksort

d. Radixsort

3. Reading:

a. Packages: Section 7.4

b. Complexity and Big-Oh Notation:
Section 5.8 and Wikipedia page on Big-Oh

c. Quicksort: Wikipedia page on Quicksort

Topics:

1. Packages (read about them)

2. Complexity:

a. Complexity = the amount of time, space, or other resources consumed.

b. Big-Oh: Asymptotic upper bound

c. Big-Omega: Asymptotic lower bound

d. Big-Theta: Asymptotic tight bound (Big-Oh and Big-Omega)

e. Basic Idea: Ignore all terms but highest term + ignore all constants

f. Examples:

i. 3n² + 2n – 8 = O(n²)

ii. 3nlogn – 12(logn)² = O(nlogn)

iii. 19log₃n = O(logn) (we can ignore the base of logarithms! Why?)

3. Quadratic Sorts

a. Worst-case is O(n²) for insertionsort, selectionsort, bubblesort

b. Average-case is O(n²) for insertionsort, selectionsort, bubblesort

c. Demonstrate mathematically and empirically

4. Fast (“nlogn”) Sort: Mergesort

a. Best/Average/Worst cases for mergesort are all O(nlogn)

b. Demonstrate mathematically and empirically

c. So? So mergesort is way faster than quadratic sorts on average

d. Insertionsort can be faster on small arrays.

e. Insertionsort and bubblesort can be faster on “mostly-sorted” arrays.

5. Another Fast (“nlogn”) Sort: Quicksort

a. Algorithm:
1. Choose a “pivot”.
2. Place pivot in the correct location, moving all elements less than or equal to the pivot to its left, and all elements greater than the pivot to its right.
3. Recursively sort elements on the left, then elements on the right of the pivot.

b. Average-case is O(nlogn), worst-case is O(n²).

c. Demonstrate mathematically and empirically.