Thursday, February 27, 2014

Sorting numbers, storing data

I wasn't there. Not a good 2 weeks for me. Blame McHacks.

1Sorting numbers¶

An analysis of quicksort. Somehow different from the one on March 13?

2Storing data¶

Hash tables and bucket size. Max bucket size is apparently $\leq 2\log(n) + 1$. Proof: uses Boole's inequality (union bound) and a whole lot of other shit