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

Introduction

Let

Sₙ=∑ { k log₂ k ∣ 2 ≤ k ≤ n-1 }

Our overall goal is to prove that for n≥2

Sₙ ≤ Bₙ ≡ ½ n² log₂ n - ⅛ n²

(from the analysis of randomized quicksort). The proof has been broken into several steps. The bound in each question may be used in following steps, whether or not you manage to prove it.

See also the general rules about assignments in this course.

DUE: 2018-01-31, 09:15 in the assignment box.

Questions

  1. Define the nth harmonic number Hₙ = ∑ { (1/i) ∣ 1 ≤ i ≤ n}. Prove that Hₙ ≤ ln n + 1. Hint: calculus.

  2. Prove that log₂(n) - log₂(n-1) ≥ 1/(2n) for n≥2

  3. Prove that ½(n²-1) log₂ (n-1) - ⅛(n-1)² ≤ Bₙ for n≥2

  4. Prove by induction that Sₙ ≤ Bₙ for n≥2