Transcript Recurrence Relations

Analysis of Algorithms &
Recurrence Relations
Recursive Algorithms
• Definition
– An algorithm that calls itself
• Components of a recursive algorithm
1. Base cases
•
Computation with no recursion
2. Recursive cases
•
•
Recursive calls
Combining recursive results
Critical Section Example 5
• Code (for input size n)
1. DoWork (int n)
2. if (n == 1)
3.
A
4. else
5.
DoWork(n/2)
6.
DoWork(n/2)
• Code execution
– A
– DoWork(n/2) 
• Time(1) 
Time(n) =
Critical Section Example 5
• Code (for input size n)
1. DoWork (int n)
2. if (n == 1)
3.
A
4. else
5.
DoWork(n/2)
6.
DoWork(n/2)
critical
sections
• Code execution
– A  1 times
– DoWork(n/2)  2 times
• Time(1)=1
Time(n) = 2  Time(n/2) + 1
Recurrence Relations
A recurrence relation is an equation that describes a
function in terms of itself by using smaller inputs
The expression:
c
n 1


T (n)  
n

2T    c n  1
  2 
describes the running time for a function contains
recursion.
5
Recurrence Relations
• Definition
– Value of a function at a point is given in terms of
its value at other points
• Examples
–
–
–
–
–
T(n) = T(n-1) + k
T(n) = T(n-1) + n
T(n) = T(n-1) + T(n-2)
T(n) = T(n/2) + k
T(n) = 2  T(n/2) + k
Recurrence Relations
• Base case
– Value of function at some specified points
– Also called boundary values / boundary
conditions
• Base case example
–
–
–
–
T(1) = 0
T(1) = 1
T(2) = 1
T(2) = k
Solving Recurrence Relations
Three general methods for solving recurrences
– Substitution method
– Iteration method (Back Substitution)
– Master method
8
Iteration Method
Iteration method:
1. Expand the recurrence k times
2. Work some algebra to express as a
summation
3. Evaluate the summation
9
Solving Recurrence Equations
• Iteratively substitute recurrence into formula
• Example
T(1) = 5
T(n) = T(n-1) + 1
SO, T(n) = O(n)
= ( T(n-2) + 1 ) + 1 = T(n-2) + 2
= ( ( T(n-3) + 1 ) + 1 ) + 1 = T(n-3) + 3
= ( ( ( T(n-4) + 1 ) + 1 ) + 1 ) + 1 =T(n-4) + 4
=…
= T(n-k) + k
STOP when n - k = 1 here (or k = n-1)
= T(n – (n-1)) + n-1
= T(1) + n-1
= 5 + n -1
=n+4
Example Recurrence Solutions
• Examples
–
–
–
–
–
–
–
T(n) = T(n-1) + k
T(n) = T(n-1) + n
T(n) = T(n-1) + T(n-2)
T(n) = T(n/2) + k
T(n) = 2  T(n/2) + k
T(n) = 2  T(n/2) + n
T(n) = 2  T(n-1) + k
 O(n)
 O(n2)
 O(n!)
 O(log(n))
 O(n)
 O(nlogn)
 O(2n)
• Many additional issues, solution methods
Iterative Factorial Algorithm
int factorial (N)
{
temp = 1;
for i = 1 to N {
temp = temp*i;
}
return(temp);
}
Time Units to Compute
------------------------------N loops.
c for the multiplication.
N
T ( N )   c  cN
i 1
Thus this requires O(N) computation.
Recursive Factorial Algorithm
int factorial (N)
{
if (N == 1) return 1;
else return(N * factorial(N-1));
Time Units to Compute
------------------------------c for the conditional
d for the multiplication and then T(N-1).
T (1)  c
T ( N )  c  d  T ( N  1)
T(N) = c+d+T(N-1) = k+T(N-1) is a recurrence relation.
How do we solve it?
Example: Factorial
T (1)  c
T ( N )  T ( N  1)  d

T ( N )  T ( N  2)  2 d
T ( N )  T ( N  k )  kd
T ( N )  T ( N  ( N  1))  ( N  1)d
T ( N )  c  ( N  1)d  O( N )
Sequential Search Algorithm
int a[N]; // An array
int value; // Value to be found
int search ( ) {
for (i = 0; i < N; i++) {
if (a[i] == value) return(i);
}
return(-1);
}
Time Units to Compute
------------------------------N loops
c for comparison
N 1
T ( N )   c  cN
i 0
Thus this is an O(N) algorithm.
Recursive Binary Search Algorithm
int a[N]; // Sorted array
int x; // Value to be found
int bin_search (int left, int right) {
if (left > right) return –1;
int mid = (left+right) / 2;
if (x < a[mid])
bin_search(left, mid-1);
else if (x > a[mid])
bin_search(mid+1,right);
else return mid;
Time Units to Compute
------------------------------c for comparison.
d for computation of mid.
c for comparison.
T(N/2)
c for comparison.
T(N/2)
}
Thus T(N) = T(N/2) + 3c+d = T(N/2)+e
T (1)  c
Analysis
(assume N  2 ...or...k  log n )
k
T(N)  T(N/ 2 )  d

T ( N )  T ( N / 4 )  2d
T ( N )  T ( N / 2 )  kd
k
STOP.when. N  2 ...or...k  log n
k
T ( N )  T ( N / 2logn )  d log N
........  T ( N / N )  d log( N )
........  T (1)  d log n  c  d log N  O (log N )
Asymptotic Notations
• O notation: asymptotic “less than”:
– f(n)=O(g(n)) implies: f(n) “≤” g(n)
•  notation: asymptotic “greater than”:
– f(n)=  (g(n)) implies: f(n) “≥” g(n)
•  notation: asymptotic “equality”:
– f(n)=  (g(n)) implies: f(n) “=” g(n)
18
Definition: (g), at least order g
Let f,g be any function RR.
• We say that “f is at least order g”, written (g), if
c,n0: f(x)  cg(x), x>n0
• “Beyond some point n0, function f is at least a constant c
times g (i.e., proportional to g).”
– Often, one deals only with positive functions and can
ignore absolute value symbols.
• “f is at least order g”, or “f is (g)”, or “f= (g)”
all just mean that f (g).
19
Big-  Visualization
20
Definition: (g), exactly order g
• If fO(g) and gO(f) then we say “g and f
are of the same order” or “f is (exactly)
order g” and write f(g).
• Another equivalent definition:
c1c2, n0: c1g(x)f(x)c2g(x), x>n0
• “Everywhere beyond some point n0, f(x) lies
in between two multiples of g(x).”
• (g)  O(g)  (g)
(i.e., fO(g) and f(g) )
21
Big-  Visualization
22
Review: Orders of Growth
Definitions of order-of-growth sets,
g:RR
•
•
•
•
•
O(g)  {f |  c, n0: f(x)  cg(x), x>n0 }
o(g)  {f | c n0: f(x) < cg(x),x>n0 }
(g)  {f| | c, n0 : f(x)  cg(x),x>n0 }
(g)  {f |  c n0: f(x) >cg(x), x>n0}
(g)  {f | c1c2, n0: c1g(x)f(x)|c2g(x),
x>n0}
23
Master Theorem
c
n 1


T ( n)  
n

aT    cn n  1
  b 
Recurrences in the form shown above can be evaluated
using a simplified version of the Master's Theorem:
 n 

T (n)  n log b n 
  n logb a



ab
c
ab
c
ab
Prove by solving in general form.
c
25
Using The Master Method
T(n) = T(n/2) + 4n
• a=1, b=2, c = 4
• 1 < 24
• Thus the solution is T(n) = (n)
T(n) = 2T(n/2) + n
• a=2, b=2, c = 1
• 2= 21
• Thus the solution is T(n) = (n log n)