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

Introduction

This assignment covers material related to divide and conquer algorithms, including use of the master theorem and the substitution method (induction).

See also the general rules about assignments in this course.

DUE: 2016-10-06, 16:30 in the assignment box.

Questions

1. Give a big-O bound for the recurrence T(n) = 3T(n/4) + sqrt(n)

  1. Using the master theorem
  2. Using a recurrence tree
  3. Using the subsitution method

2 Describe a family of inputs with unique elements that is neither sorted nor reverse sorted such that quicksort (with pivot chosen as the first element in the sub-array being sorted) is Θ(n²).