Scribd
Upload
9 views

Design and Analysis Algorithm

Uploaded by

Samsung A12
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
9 views

Design and Analysis Algorithm

Uploaded by

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

Design and

Analysis
Algorithm
The Recurrence
and its example and
problem solutions

*
Presented by BSCS-E1 (girls)

(Roll no 4,5,7,9,15,19, 20)

Designed by Sara Yousaf


THE RECURSION

• The process in which the function calls itself is called


recursion
• The corresponding function is called the recursive function.

• In recursion one function called itself, the number of parameters


never
changes only the parameter value changes

For example:
Fact(4)=24
• Solution:
4*fact(3)
4*3*fact(2)
4*3*2*fact(1)
4*3*2*1=24
The Recursion

Advantages: Disadvantages:
• Recursion adds clarity to the code. • Uses more memory
• It can reduce time complexity • Recursion becomes slow
• Reduce time to debug • A recursive program has a greater
• It is also used for analyzing and space
optimizing the algorithm requirement than an iterative program
as each function in the program
remains
in the stack until the base case is
reached
THE RECURRENCE
• Recurrence is an equation or an in-
equality that describes the function in
terms of its smaller inputs
• Recurrences arise when an algorithm
contain recursive calls to itself.
The simplest form is as follows:

T(n)= T(n-1)+n
The Recurrence
• Binary Search:
1 2 3 4 5 6 7 8

T(n)=T(n/2)+1
Signifies a function
Input size
1 2 3 4 5 6 7 8
T(n)=T(n/2)+1
Reducing of input 2 3 5 7 9 10 11 12
size

Mid =[(lo+hi)/2]
Exp; lo
mid pt= 4 approx mid hi
Example:
The Recurrence A[8]={1,2,3,4,5,7,9,11} midpoint
-lo=1 ,hi=8,x=7
• Binary Search:
Binary Search (A, lo, hi, x)
1 2 3 4 5 6 7 8
 if(lo>hi)
return false 1 2 3 4 5 7 9 11
mid=4, lo=5 , hi=8
mid (lo+hi)/2
 If x=A[mid]
return True
1 2 3 4 5 6 7 8
 If(x<A[mid])
Binary-Search(A,lo,mid-1,x) 1 2 3 4 5 7 9 11

 If(x>A[mid])
mid=6, A[mid]=x Found!
Binary-Search(A,mid+1,hi,x)
midpoint
Exp-2:
Exp-1:
int binarySearch(intarr[],int n , int key) //O(1)
• Simple code {
int low=0; //O(1)
void fun(int n) //O(1)
int high=n-1;
{ n //O(log n)
while(low<=high){
if(n>0){
1 //O(1)
int mid=(low+high)/2; //O(1)
THE for(i=0;i<n;i++) n+1 if(arr[mid]==key) { //O(1)
RECURRENCE { return mid; }
print(n);{ n
fun(n-1)} else if (arr[mid]<key) {
n-1 //O(1)
} low=mid+1; }
else {
//O(1)
high= mid-1; } }
T(n)=T(n-1)+2n+2 return -1; } //O(1)
T(n)=T(n-1)+n
T(n)=O(1)+)O(1)+O(logn)*(O(1)+O(1)+O(1))+O(1)
T(n)=O(1)+O(1)+O(logn)+O(1)+O(1)
T(n)=O(logn)

You might also like