Advanced Algorithm Analysis
Assignment 1
Deadline: Tuesday 15th October 2024
Master theorem is a quick-fix solution to find the time complexity of a recursive algorithm
particularly divide and conquer algorithms. It says that if a divide and conquer algorithm
divides a problem into a subproblems each of size b and that the cost to conquer and combine
is f (n) = Θ(nd ) then we have a recursive relationship that looks like this
T (n) = a × T (n/b) + f (n)
and
T (1) = c
such that a ≥ 1, b > 1, c ≥ 1, d ≥ 0
Master theorem makes it easy to solve this recursive relationship through the following
formula:
d
Θ(n )
if a < bd
T (n) = Θ(nd log n) if a = bd (1)
logb a
Θ(n ) otherwise
You have read more in the textbook as well as on the internet. Once you are comfortable
with the master theorem, please solve the following question:
Question 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 points
What is the time complexity of a recursive algorithm with the following recursive time
complexity equation? Show working.
T (n) = 3T (n/2) + 3/4n + 1
Question 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 points
What is the time complexity of a recursive algorithm with the following recursive time
complexity equation? Show working.
√
T (n) = 2T (n/4) + n + 42
Question 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 points
What is the time complexity of a recursive algorithm with the following recursive time
complexity equation? Show working.
1
T (n) = T (n/2) + × n2 + n
2
