## Introduction

This assignment is to remind you of the background material you from the prerequisite courses. We will not need all of this right away, but if you find one of these questions particularly difficult, that's a hint to do some background reading.

See also the general rules about assignments in this course.

**DUE**: 2016-09-15, 16:30 in the assignment box.

## Questions

Prove formally that

*n log₂(n) ∈ O(n²)*, i.e. give constants*c*and*n₀*and show that for all integers*n≥n₀*,*n log₂(n) ≤ cn²*. Use induction in your proof.Analyse the worst case time complexity of bubblesort. Give an upper (i.e. O) bound. The key idea is to show that each pass makes some measurable progress.

Suppose you have

*n*buckets and*k*items. Each item is placed in a (uniform) random bucket. What is the expected number of empty buckets?