 In Progress
Lesson 16 of 43
In Progress

# Recurrence Equation for Divide and Conquer

Divide-and-conquer algorithms:

1. Dividing the problem into smaller sub-problems
2. Solving those sub-problems
3. Combining the solutions for those smaller subproblems 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.

• 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))

## 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) + cnd 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.

Example :

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

Solution:
a=1, b=2, c=4 and d=0
So, a = b^d = 1.
By Master theorem, T(n) = theta(n^d log n) = theta(log n)

Example:

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

Solution:
a=2, b=2, c=1 and d=0
So, a > b^d = 1.
By Master theorem, T(n) = theta(n^logba) = theta(n^log22) = theta(n).