CMPSC 465 Data Structures & Algorithms
Fall 2021 and Worksheet 4
Monday, September 20, 2021
1. Recurrence Relations Solve the following recurrence relations and give a bound for each of them.
Give a short justification for each of your answers.
a) T (n) = 4T (n/2)+42n
b) T (n) = 2T (2n/3)+T (n/3)+n2
c) T (n) = 3T (n/4)+n logn
d) T (n) = 7T (n/2)+n2 + logn
e) T (n) = T (n−1)+n3
Solution:
a) T (n) = 4T (n/2)+42n
Use the master theorem. Or:
42n
uu || “” ))
21n 21n 21n 21n
…
The first level sums to 42n, the second sums to 84n, etc. The last row dominates, and we have
logn rows, so we have 42 ·2logn ·n = Θ(n2).
b) T (n) = 2T (2n/3)+T (n/3)+n2
If you visualize it as a tree you get:
n2
uu �� ))
Sum: n2
(23 n)
2
�� �� ��
(23 n)
2
�� �� ��
(13 n)
2
�� �� ��
Sum: n2
(23
2
3 n)
2 (23
2
3 n)
2 (23
1
3 n)
2 (23
2
3 n)
2 (23
2
3 n)
2 (23
1
3 n)
2 (13
2
3 n)
2 (13
2
3 n)
2 (13
1
3 n)
2 Sum: n2
…
So the answer is: Θ(n2 logn).
CMPSC 465, Fall 2021, Worksheet 4 1
c) T (n) = 3T (n/4)+n logn
On expanding the recurrence we get
T (n)= n logn+3T (n/4)= n logn+3(
n
4
log
n
4
+3T (
n
16
))= n logn+3
n
4
log
n
4
+9
n
16
log
n
16
+. . .
Thus, we can see that we end up with ∑
log4 n
i=0 (
3
4)
in log n4i . We can lower-bound this by n logn
by taking the first term, and upper-bound it by n logn be replacing log(n/4i) by logn, so this is
Θ(n logn).
d) Applying Master Theorem, we see that a= 7, b= 2, and d = 2. Since logb a= log2 7≈ 2.81> 2,
we get T (n) = Θ(nlogb a) = Θ(nlog2 7).
e) T (n) = T (n−1)+n3 = ∑ni=1 i
3 +T (0) = O(n3+1) = O(n4)
2. Recurrence Relations
a) Algorithm A solves problems by dividing them into five subproblems of half the size, recursively
solving each subproblem, and then combining the solutions in linear time.
b) Algorithm B solves problems of size n by recursively solving two subproblems of size n−1 and
then combining the solutions in constant time.
c) Algorithm C solves problems of size n by dividing them into eight subproblems of size
n
4
,
recursively solving each subproblem, and then combining the solutions in O(n3) time.
What are the running times of each of these algorithms (in big-O notation), and which would you
choose as the fastest?
Solution:
a) T (n) = 5T (n2) +O(n) . This is a case of the Master theorem with a = 5,b = 2,d = 1. As
logba > d, the running time is O(nlogb a) = O(nlog2 5) = O(n2.33).
b) T (n) = 2T (n−1)+C, for some constant C. T (n) can then be expanded to C ∑n−1i=0 2
i+2nT (0) =
O(2n).
c) T (n) = 8T (n4)+O(n
3) . Thus we have a = 8,b = 4,d = 3. As logba < d, we get O(n3)
The sorted order by complexity will be A
2. Else if pivot is on the right half then the middle will be of a greater value than the end arr[mid+
1]> arr[end]
CMPSC 465, Fall 2021, Worksheet 4 3
Pseudo code:
while start < end do
mid⇐ b(start + end)/2c
if arr[mid]> arr[mid +1] then
return arr[mid]
end if
if arr[mid−1]> arr[mid] then
return arr[mid−1]
end if
if arr[start]> arr[mid−1] then
end = mid−1
else
start = mid +1
end if
end while
CMPSC 465, Fall 2021, Worksheet 4 4