Divide & Conquer Recurrence Relations | Algorithms - Computer Science Engineering (CSE) PDF Download

Divide-and-conquer algorithms

• Dividing the problem into smaller sub-problems
• Solving those sub-problems
• Combining the solutions for those smaller sub - problems to solve the original problem

Recurrences are used to analyze the computational complexity of divide-and-conquer algorithms.

Example: Binary search is a divide-and-conquer algorithm.

Divide-and-conquer recurrence

• Assume a divide-and-conquer algorithm divides a problem of size n into a sub-problems.
• Assume each sub-problem is of size n/b.
• Assume f(n) extra operations are required to combine the solutions of sub-problems into a solution of the original problem.
• Let T(n) be the number of operations required to solve the problem of size n.
  T(n) = a T(n/b) + f(n)
  In order to make the recurrence well defined T([n/b]) term will actually be either T([n/b]) or T([n/b]).
  The recurrence will also have to have initial conditions. (e.g.T(1) or T(0))

Example: Binary search

Example: Finding the maximum and minimum of a sequence:
Consider the sequence a1, a2, …, an.
If n=1, then a1 is the maximum and the minimum.
If n>1, split the sequence into two sequences, either where both have the same number of
elements or where one of the sequences has one more element than the other.
The problem is reduced to finding the maximum and minimum of each of the two smaller sequences.
The solution to the original problem results from the comparison of the separate maxima and minima of the two smaller sequences.
Find a recurrence T(n) that be the number of operations required to solve the problem of size n.

The problem of size n can be reduced into two problems of size [n/2] and [n/2].
Two comparisons are required to find the original solution from those sub-problems.
T(1) = 1 T(n) = T([n/2]) + T([n/2]) + 2

Example: Merge sort
The merge sort algorithm splits a list with n elements into two list with [n/2] and [n/2] elements.
(The list with 1 element is considered sorted.) It uses less than n comparison to merge two sorted lists of [n/2] and [n/2] elements.
Find a recurrence T(n) that represents the number of operations required to solve the problem of size n. (The merge sort may have less operations than T(n))

The problem of size n can be reduced into two problems of size [n/2] and [n/2]. n comparisons are required to find the original solution from those subproblems.
T(1) = 1 T(n) = T([n/2]) + T([n/2]) + 2

Master theorem

There is a theorem that gives asymptotic behavior of any sequence defined by a divide-and-conquer recurrence with f(n)=c.n^d for constants c>0 and d>0.
This theorem is sometimes called the master theorem.

Theorem: Assume a sequence is defined by a recurrence equation

T(n) = aT(n/b) + cn^d for n>1,
where a>1, b>2, c>0 and d>0 are constants and n/b is either [n/b] or [n/b], then one of the following holds.
T(n) = Θ(n^d) if a < b^d
T(n) = Θ(n^d log n) if a = b^d
T(n) = Θ(n^logba) if a > b^d

Example 1: Assume an algorithm behavior is determined using the following recurrence.Give big-Theta estimate for its complexity.
T(1) = 1
T(n) = T([n/2]) + 4, for [n/2]

a=1, b=2, c=4 and d=0
So, a = b^d = 1.

By Master theorem, T(n) = Θ(n^d log n) = Θ(log n) .

Example 2: Assume an algorithm behavior is determined using the following recurrence.Give big-Theta estimate for its complexity.

T(1) = 0

T(n) = T([n/2]) + T([n/2]) + 1, for n>2

a=2, b=2, c=1 and d=0

So, a > b^d = 1.

By Master theorem, T(n) = Θ(n^logb^a) = Θ(n^log₂²) = Θ(n).

Example 3: Assume an algorithm behavior is determined using the following recurrence.Give big-Theta estimate for its complexity.

x₀ = 0
x_n = 7x_[n/5] + 9n², for n>1

a=7, b=5, c=9 and d=2
So, a < b^d = 25

By Master theorem, T(n) = Θ(n^d) = Θ(n²).

Example 4: Give big-Theta estimate for the merge sort algorithm.

By previous example, we know the following recurrence represent the merge sort algorithm.

T(1) = 0

T(n) = T([n/2]) + T([n/2]) +n for n>1.

a=2, b=2, c=1 and d=1
So, a = b^d = 2.

By Master theorem, T(n) = Θ(n^d log n) = Θ(n log n)

Example 5: Give big-Theta estimate for following recurrence.
f(n) = 2f(√n + 1 when a perfect square n >1,

f(2)=1.
(Hint: assume m = log2 n.)

m = log₂n     2^m = n
f(2^m) = 2f((2^m)^1/2) + 1 f(2^m) = 2 f(2^m/2) + 1
g(m) = 2 g(m/2) + 1
a=2, b=2, c=1 and d=0
So, a > b^d = 1.

By Master theorem, g(m) = Θ(m^logba) =
(m^log₂²) = Θ(m).

So, f(n) = Θ(log₂ n).