Scribd
Upload
68 views11 pages

05 Recursive Algorithms Intro

This document discusses recursive algorithms and merge sort. It explains that recursive algorithms use a divide and conquer approach by dividing a problem into smaller subproblems, solving those subproblems recursively, and combining the results. Merge sort is presented as an example, dividing an array in half, sorting the halves recursively, and merging the sorted halves. The document analyzes the runtime of merge sort and discusses different methods for solving recurrence relations that model algorithm runtimes, such as substitution method, recursion tree method, and master method.

Uploaded by

Muhammad Rifki
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
68 views11 pages

05 Recursive Algorithms Intro

This document discusses recursive algorithms and merge sort. It explains that recursive algorithms use a divide and conquer approach by dividing a problem into smaller subproblems, solving those subproblems recursively, and combining the results. Merge sort is presented as an example, dividing an array in half, sorting the halves recursively, and merging the sorted halves. The document analyzes the runtime of merge sort and discusses different methods for solving recurrence relations that model algorithm runtimes, such as substitution method, recursion tree method, and master method.

Uploaded by

Muhammad Rifki
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

Recursive Algorithms

 Prima Dewi Purnamasari


Divide-and-conquer paradigm
 Divide the problem into a number of subproblems that
are smaller instances of thesame problem.
 Conquer the subproblems by solving them recursively.
 Base case: If the subproblems are small enough, just solve
them by brute force.
 Combine the subproblem solutions to give a solution to
the original problem.

2
Merge Sort (1/5)
 Divide: Divide the n-element sequence to be sorted into
two subsequences of n=2 elements each.
 Conquer: Sort the two subsequences recursively using
merge sort.
 Combine: Merge the two sorted subsequences to
produce the sorted answer.

The recursion “bottoms out” when the sequence to be


sorted has length 1

3
Merge Sort (2/5)

Divide and conquer

Combine

The MERGE procedure takes time ϴ(n), where n = r - p + 1 is the


total number of elements being merged

4
Merge Sort (3/5)

5
Merge Sort (4/5)
The divide and conquer part

6
Merge Sort (5/5)
 Divide: The divide step just computes the middle of the subarray,
which takes constant time. Thus, D(n) = ϴ(1)
 Conquer: We recursively solve two subproblems, each of size n=2,
which contributes 2T(n/2) to the running time.
 Combine: We have already noted that the MERGE procedure on an
n-element n and so C(n) = ϴ(n)

Intuitively by the tree illustration: T (n) = n lg n

7
Recurrence asymptotic notation

8
How?

9
Methods
Three methods for solving recurrences—that is, for
obtaining asymptotic “ϴ” or “O” bounds on the solution:
 The substitution method, we guess a bound and then
use mathematical induction to prove our guess correct.
 The recursion-tree method converts the recurrence into
a tree whose nodes represent the costs incurred at
various levels of the recursion.
 The master method provides bounds for recurrences of
the form

10
Group discussion
• The substitution method
• The recursion-tree method
• The master method

11

You might also like