CS3230 Semester 2 2025/2026
Design and Analysis of Algorithms
Tutorial 02
Recurrences and Master Theorem
For Week 03
Document is last modified on: January 20, 2026
1 Lecture Review: Recurrences
Given a recurrence in the form of T (n) = a · T ( nb ) + f (n), where f (n) = c · nm logk n, we want to give
a tight asymptotic bound for T (n).
There are a few ways to solve recurrences, with the easiest being the Master theorem (master
method). Let d = logb a (this d plays an important role; also notice bd = a).
1. Case 1: f (n) ∈ O(nd−ϵ ) ⇒ T (n) ∈ Θ(nd ).
The work done at the leaves dominates.
2. Case 2: f (n) ∈ Θ(nd logk n) ⇒ T (n) ∈ Θ(nd logk+1 n).
Balanced contributions at all levels.
There are some extensions of case 2, to be elaborated in this tutorial.
3. Case 3: f (n) ∈ Ω(nd+ϵ ) ⇒ T (n) ∈ Θ(f (n)),
assuming, for some constant c < 1, that for all x, a · f ( xb ) ≤ c · f (x) (regularity condition).
The work done at the root dominates.
However, there are at least three other ways to solve recurrences, especially useful when the recur-
rences are not of the form stated above: Telescoping (if applicable), substitution method (guess and
check; need good guess(es)), or draw the recursion tree (try exploring [Link]
recursion).
1.1 Recap About Telescoping
Pn−1
Consider any sequence a0 , a1 , . . . , an and suppose we need to find i=0 (ai − ai+1 ).
Pn−1
Expanding i=0 (ai − ai+1 ), we have (a0 − a1 ) + (a1 − a2 ) + (a2 − a3 ) + . . . + (an−1 − an ).
1
Which can be rewritten as a0 + (−a1 + a1 ) + (−a2 + a2 ) + . . . + (−an−1 + an−1 ) − an .
Thus, except for a0 at the beginning and −an at the end, all other ai appear exactly once as a negative
Pn−1
and then as a positive in the sum, and thus cancel each other, making i=0 (ai − ai+1 ) = a0 − an .
2 Tutorial 02 Questions
Q1). Give a tight asymptotic bound for T (n) = 4 · T ( n4 ) + n
log n using telescoping.
Q2). Give a tight asymptotic bound for T (n) = 5 · T ( n3 ) + n.
1. T (n) ∈ Θ(n2 )
2. T (n) ∈ Θ(nlog5 3 )
3. T (n) ∈ Θ(nlog3 5 )
4. T (n) ∈ Θ(n log n)
5. T (n) ∈ Θ(n)
Q3). Give a tight asymptotic bound for T (n) = 9 · T ( n3 ) + n3 .
1. T (n) ∈ Θ(n9 )
2. T (n) ∈ Θ(n3 log n)
3. T (n) ∈ Θ(n2 )
4. T (n) ∈ Θ(n3 )
5. T (n) ∈ Θ(n log2 n)
Q4). Give a tight asymptotic bound for T (n) = 16 · T ( n4 ) + n2 log n.
1. T (n) ∈ Θ(n2 log n)
2. T (n) ∈ Θ(n2 log2 n)
3. T (n) ∈ Θ(n2 )
4. T (n) ∈ Θ(n3 )
5. T (n) ∈ Θ(n4 log n)
√
Q5). Give a tight asymptotic bound for T (n) = 4 · T ( n2 ) + n using the substitution method.
Q6). Suppose that you are given k sorted arrays: {A1 , A2 , . . . , Ak }, with n elements each.
Your task is to merge them into one combined sorted array of size k · n.
Let T (k, n) denotes the complexity of merging k arrays of size n.
Suppose that you decide that the best way to do the above is via recursion (when k > 1):
2
1. Merge the first ⌈ k2 ⌉ arrays of size n,
2. Merge the remaining ⌊ k2 ⌋ arrays of size n,
3. Merge the two sorted subarrays obtained from the first two steps above.
Give a formula for T (k, n) based on the recursive algorithm above and solve the recurrence. You can
assume that merging two arrays takes time proportional to the sum of the sizes of the two arrays.