# Homework Assignment #3 CMPUT 204 solution

\$30.00

Category:

## Description

In all problems, we assume T(n) = O(1) for small n.
Problem 1. (20 marks)
 Use iterated substitution to guess a good solution (a tight asymptotic upper bound) to the recurrence
T(n) = T(n−10)+n and prove your guess is indeed a solution. What about T(n) = T(n−100)+100n?
No justification is required (hope you can answer this question immediately with confidence).
 Show the solution to T(n) = 2T(bn/2c + 8) + n is O(n log n).
 Given the recurrence T(n) = T(n/3) + T(2n/3) + 3n, use the recurrence tree method to guess a
tight upper bound and a tight lower bound and prove that your guesses are correct (to simplify the
question, for this latter part, you only need to present a proof either for the upper bound or for the
lower bound).
 Solve the recurrence T(n) = 2T(

n) + log log n. Hint: You may consult any solutions you can find
online for CLRS 4.3-9.
 Solve the recurrence T(n) = 2T(n − 2) + 1. You can use any method to guess a tight solution (you
only need to sketch how you guessed) and then prove your guess is correct.
Problem 2. (8 marks) Apply the master method to solve the following recurrences.
a) T(n) = 8T(n/4) + n
2
.
b) T(n) = 5T(n/9) + √
n.
c) T(n) = 2T(n/4) + 1.
d) T(n) = 9T(n/8) + n
2 + n.
Problem 3. (12 marks) Consider the following very simple and elegant(?) sorting algorithm:
SomeSort (A, b, e)
if e = b + 1 then
if A[b] > A[e] then
exchange A[b] and A[e]
end if
else if e > b + 1 then
p ←− b e−b+1
3
c
SomeSort (A, b, e − p)
SomeSort (A, b + p, e)
SomeSort (A, b, e − p)
end if
1
a. Does SomeSort correctly sort its input array A (assuming that n = e−b+ 1 is the length of the array)?