Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Lower bounds, revisited.
• Other techniques.
• Bucket sort.
• Radix sort.

Preliminaries

Admin

• No class on Friday, October 16
• PMO on Wednesday, October 14
• How many of you already know bucket sort and radix sort?

Upcoming Work

• For Friday: Chapter 4 of Skiena
• For next Wednesday: Exam 1

Extra Credit

• Don't forget that you can send these to me in advance!

Academic

• CS Table Thursday: Blake
• CS Table Tuesday at noon: Health

Peer

• Women's Soccer Saturday at noon against Monmouth
• Women's Soccer Saturday at 2:30 against Monmouth
• Loose Show Midnight 10/10 to 10/11
• Harry Potter FanFic Event Saturday at 3pm

Questions

Lower bounds, revisited

We saw that the best we can do on a comparison-based sort was O(log(n!)) = O(log(2^(nlogn))) = O(nlogn)

Sam gave a mediocre proof that n! =~ 2^nlogn

We're going to prove something more directly relevant

log(n!) is in Theta(nlogn)

log(n!) is in O(nlogn)

log(n!) is in Omega(nlogn)

• (1) log(n!) = log(n(n-1)(n-2)...32*1) ; by definition
• (2) log(a*b) = log(a) + log(b) ; Lemma
• (3) log(n!) = log(n) + log(n-1) + log(n-2) + ... + log(2) + log(1)

log(n!) is in O(nlogn)

• (4) If a > b >= 1, log(a) > log(b) >= 0 ; Def'n of log
• (5) log(n!) < log(n) + log(n) + log(n) + .... + log(n) + log(n)
• (6) log(n!) < nlog(n)
• (7) log(n!) is in O(nlogn), c = 1, n0 = 2

log(n!) is in Omega(nlogn)

• (8) log(n!) = log(n) + log(n-1) + ... log(n/2) + log(n/2-1) + ... + log(1)
• (9) log(n!) > log(n/2) + log(n/2) + ... log(n/2) + log(2) + ... + log(2) + log(1)
• (10) log(n!) > n/2log(n/2) + n/2(log(2))
• (11) log(n!) > n/2*(log(n)-log(2)) + n/2(log(2))
• (12) log(n!) > n/2*logn
• (13) log(n!) is in Omega(nlogn), c = 1/2 n0 = ?

Problem! We cheated

• (14) log(n!) = log(n) + log(n-1) + ... log(n/2) + log(n/2-1) + ... + log(1)
• (15) log(n!) > n/2*log(n/2) + log(n/2-1) + log(n/2-2) + ... + log(1)
• (16) log(n!) > n/2log(n/2) + log(n/2-1) + (n/2-2)log(2)
• (17) log(n!) > n/2(log(n)-log(2)) + log(n/2-1) + (n/2-2)1
• (18) log(n!) > n/2*log(n)-n/2 + log(n/2-1) + n/2-2
• (19) log(n!) > n/2*log(n) + log(n/2-1) -2
• (20) if log(n/2-1) > 2, we're fine, n>11
• (21) log(n!) is in Omega(nlogn), c = 1/2, n0=11

Other techniques

Think about

• I'm sorting a list of 10000 integer grades, all in the range 0..100
  • Idea: If you have few distinct values and you can quickly determine which value it is, just put them in that "bucket" (linked list)
• I'm sorting a list of 10000 non-negative integers
  • Idea: Look at the bit representation!
• Other issues:
  • Idea: Use O(n) extra memory! It's worth it.

Bucket sort

Radix sort