Computer Science Engineering (CSE) Exam  >  Computer Science Engineering (CSE) Notes  >  Algorithms  >  Divide & Conquer Recurrence Relations

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

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

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

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.nd 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.
T(n) = Θ(nd) if a < bd
T(n) = Θ(nd log n) if a = bd
T(n) = Θ(nlogba) if a > bd

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 = bd = 1.

By Master theorem, T(n) = Θ(nd 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 > bd = 1.

By Master theorem, T(n) = Θ(nlogba) = Θ(nlog22) = Θ(n).

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

x0 = 0
xn = 7x[n/5] + 9n2, for n>1

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

By Master theorem, T(n) = Θ(nd) = Θ(n2).

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 = bd = 2.

By Master theorem, T(n) = Θ(nd 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 = log2n     2m = n
f(2m) = 2f((2m)1/2) + 1 f(2m) = 2 f(2m/2) + 1
g(m) = 2 g(m/2) + 1
a=2, b=2, c=1 and d=0
So, a > bd = 1.

By Master theorem, g(m) = Θ(mlogba) = (mlog22) = Θ(m).

So, f(n) = Θ(log2 n).

The document Divide & Conquer Recurrence Relations | Algorithms - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Algorithms.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)
81 videos|80 docs|33 tests

Top Courses for Computer Science Engineering (CSE)

81 videos|80 docs|33 tests
Download as PDF
Explore Courses for Computer Science Engineering (CSE) exam

Top Courses for Computer Science Engineering (CSE)

Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
10M+ students study on EduRev
Related Searches

past year papers

,

video lectures

,

Exam

,

study material

,

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

,

Objective type Questions

,

mock tests for examination

,

Extra Questions

,

shortcuts and tricks

,

Sample Paper

,

ppt

,

Semester Notes

,

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

,

Previous Year Questions with Solutions

,

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

,

Free

,

pdf

,

practice quizzes

,

Viva Questions

,

Summary

,

Important questions

,

MCQs

;