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: 2018-01-10, 09:15AM in the assignment box.
Questions
Prove by induction that for n ≥ 4, n² ≤ 2ⁿ
Prove formally that n log₂ n ∈ O(n²), i.e. give constants c and n₀ and show that for all n≥n₀, cn² ≥ n log₂ n. One approach uses the result of the previous question.
Analyze the asymptotic running time of binary search. Be careful to avoid plagiarism of this standard result.
Suppose the President of UNB (uniformly) randomly shuffles the offices of all of the professors. Use indicator variables and linearity of expectation to compute the expected number of professors that stay in their current office.