UNB/ CS/ David Bremner/ teaching/ cs3383/ assignments/ CS3383 Assignment 0

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

  1. 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.

  2. 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.

  3. 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?