Scribd
Upload
4 views6 pages

Recursion

The document introduces algorithm design with a focus on recursion and mathematical induction. It explains how to prove the correctness of a recursive algorithm that finds the maximum element in an array using inductive reasoning. Additionally, it derives the exact solution to a recurrence relation, concluding that T(n) = n log n.

Uploaded by

thisisnotme0109
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
4 views6 pages

Recursion

The document introduces algorithm design with a focus on recursion and mathematical induction. It explains how to prove the correctness of a recursive algorithm that finds the maximum element in an array using inductive reasoning. Additionally, it derives the exact solution to a recurrence relation, concluding that T(n) = n log n.

Uploaded by

thisisnotme0109
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

UNIT I

INTRODUCTION TO ALGORITHM
DESIGN
Recursion recall
⚫ Functions calls itself
⚫ consists of one or more base cases and
one or more recursive cases.
Mathematical Analysis - Induction
⚫ Consider a recursive algorithm to compute the
maximum element in an array of integers.
⚫ You may assume the existence of a function “max(a,b)”
that returns the maximum of two integers a and b .
Solution
⚫ Let p(n) stand for the proposition that Algorithm finds and returns the maximum
integer in the locations A[1] through A[n]. Accordingly, we have to show that (∀n)
p(n) is true.
⚫ BASIS: When there is only one element in the array , i.e., n=1, then this element is
clearly the maximum element and it is returned on Line 2. We thus see that p(1) is
true.
⚫ INDUCTIVE STEP: Assume that Algorithm finds and returns the maximum
element, when there are exactly k elements in A.
⚫ Now consider the case in which there are k + 1 elements in A. Since (k + 1) > 1,
Line 4 will be executed.
⚫ From the inductive hypothesis, we know that the maximum elements in A[1]
through A[k] is returned. Now the maximum element in A is either A[k+1] or the
maximum element in A[1] through A[k] (say r). Thus, returning the maximum of
A[k+1] and r clearly gives the maximum element in A, thereby proving that p(k) →
p(k+1).
⚫ By applying the principle of mathematical induction, we can conclude that (∀n) p(n)
is true, i.e., Algorithm is correct.
⚫ Find the exact solution to the recurrence
relation using mathematical induction
method

⚫ Solution is T(n)=nlogn
Solution
⚫ Basis: At n = 1, both the closed form and the recurrence
relation agree (0=0) and so the basis is true.
⚫ Inductive step: Assume that T(r) = rlogr for all 1≤ r ≤ k . Now
consider T(k+1). As per the recurrence relation, we have,

⚫ We can therefore apply the principle of mathematical induction


to conclude that the exact solution to the given recurrence is
nlogn.

You might also like