Module 03 (Week 3)

Thursday, May 23, 2013

10:14 AM

- Distinct keys
- Arbitrary order
- Array in ascending order
- K = n-1
- Need to consider
- All inputs of a certain size and take average
- Sum runtimes of all inputs
- Divide by # of inputs
- Behaviour of algorithm on relative ordering of keys
- Not actual values
- Uniform distribution
- Each permutation is equally likely
- Each pivot location is equally likely

Selection

Quick select

Worst Case:

Average case

We'll count comparisons

Assumption 1: keys are distinct

Assumption 2:

After partition

Remember cases:

Created with Microsoft OneNote 2010

One place for all your notes and information