## Introduction

This assignment covers material related to divide and conquer algorithms, mainly recursion

See also the general rules about assignments in this course.

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

## Questions

**1** For each of the following recursion relations, if it can be
solved by the master theorem, solve it, otherwise explain why the
master theorem can not be used.

- T(n) = 2T(n/3) + 1
- T(n) = 1.5T(n/3) + sqrt(n)
- T(n) = T(log(n)) + 1
- T(n) = 8T(n/2) + n³ +101n² - 3n

**2** Solve the recurrence `T(n)=T(sqrt(n))+1`

.

**3** Consider merging `k`

sorted arrays, each of size `n`

- Give an efficient divide and conquer algorithm for this problem.
Give a recurrence relation for the worst case running time of your algorithm.

Solve the recurrence.