Recurrence Relation Tutorial

RESOURCES

C251 Text: Discrete Mathematics and Its Applications by Kenneth Rosen

The Design and Analysis of Algorithms by Anany Levitan

http://www.research.att.com/~njas/sequences - Type in a few sequence terms and finds the closed form, if one exists. Try: 1, 3, 6, 10

OVERVIEW

We are interested in determining the running time behavior of algorithms expressed as bounds using Θ or O representation. The diagram at right reflects the overall approach for analyzing an algorithm.

Recurrence relations result naturally from the analysis of recursive algorithms, specifying the algorithm's run time; solving recurrence relations yields a closed-end formula for calculation of run time.

For example, the recursive n! algorithm of:

int factorial (int n) {    if (n == 1) return 1;    return factorial (n-1) * n; }

The running time, T(n), can be defined as recurrence:

T(1) = 1 T(n) = T(n-1) + 1 for all n>1

where 1 is the running time for each execution of the factorial function.

Solving the recurrence by recognizing the summation leads to closed-end formula:

T(n) = T(1) + 1 + ... + 1 = 1 + 1 + ... + 1 = n

The run time for execution of factorial can now be directly computed for a given n.

T(10) = 10.

More importantly, when expressing the worst case run time bounds we can then write:

           | O(1) if n=1
T(n) = |
           | O(n) if n>1

SEQUENCES AND RECURRENCE RELATIONS

Sequence - a numerical, ordered list of numbers

In the following

T - a recurrence function defining a sequence

n - a parameter to function T

T(n) -  the sequence term generated by function T for parameter n

Example

T(n) = T(n-1) + n       for n > 0	B1
T(0) = 0	B2

Generate sequence values

T(0) = 0

T(1) = T(1-1) + 1 = 0 + 1 = 1

T(2) = T(2-1) + 2 = T(1) + 2 = 1 + 2 = 3

T(3) = T(3-1) + 3 = T(2) + 3 = 3 + 3 = 6

T(4) = T(4-1) + 4 = T(3) + 4 = 6 + 4 = 10

Examples

T(0) = 0 T(n) = T(n-1) + 1 T(n) 1 2 3 4 n 1 2 3 4 n-1 0 1 2 3	T(0) = 0 T(n) = T(n-1) + 2 T(n) 2 4 6 8 n 1 2 3 4 n-1 0 1 2 3	T(0) = 0     T(1) = 1 T(n) = T(⌊n/2⌋) + n T(n) 0 1 3 4 6 7 9 10 n 0 1 2 3 4 5 6 7 ⌊n/2⌋ 0 0 1 1 2 2 3 3 Question 4.1 - What is T(13)?	T(0) = 0    T(1) = 1 T(n) = T(⌈n/2⌉ ) + n T(n) 0 1 3 5 6 8 9 11 n 0 1 2 3 4 5 6 7 ⌈n/2⌉ 0 1 1 2 2 3 3 4
T(0) = 0 T(n) = T(⌊n/4⌋) + n T(n) 0 1 2 3 5 6 7 8 10 11 12 13 15 16 17 18 21 22 23 24 26 27 28 29 31 n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 ⌊n/4⌋ 0 0 0 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 ⌈n/4⌉ 0 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 Question 4.2 - What is T(97)?

Inductive proofs on the recurrence: T(n) = T(n-1) + 1

Typically assume the case for parameter n that generates a sequence term for recurrence T(n) and prove T(n+1)

T(n) = T(n-1) + 1

T(n+1)=T((n+1)-1)+1 = T(n) + 1

 

Assuming the problem size is a multiple of 2, n = 2^k,

T(1) = 1

T(n) = T(n/2) + n

T(2^k) = T(2^k/2) + 2^k = T(2^k-1) + 2^k

T(n)	1	3	7	15	31	63	127
n	1	2	4	8	16	32	64
k	0	1	2	3	4	5	6

Question 4.3    For above recurrence:

• What is the next value of n after 64?
   

• What is the next term after T(2^k)?

 

Notation

Either T_n or T(n) which stresses that a sequence is a function where T(n) is the generic nth term.

Defining a sequence (two ways)

• Closed-end formula of generic term as a function of n

  T(n) = 2n for n ≥ 0

• Recurrence equation relating generic term to one or more other sequence terms combined with one or more explicit values of first term(s).

  T(n) = T(n-1) + n       for n > 0	B1
  T(0) = 0	B2

B1 above is a recurrence relation, where the generic term, T(n), is defined by other sequence terms, T(n-1)+n.

B2 above is an initial condition

 

Recurrence Relation

Example: Fibonacci sequence definition:

int fibonacci (int n) {   if( n==0 || n==1 ) return n;   return fibonacci(n-1) + fibonacci(n-2); }

has the corresponding recurrence:

F(0) = 0                                             Initial F(1) = 1                                             Initial  F(n) = F(n-1) + F(n-2) for n>1           Recurrence

 

Solve Recurrence Relation - find closed-end formula for generic nth term of sequence that satisfies both the recurrence term and initial condition or prove that the sequence does not exist.

Example

T(n) = T(n-1) + n for n>0	B1
T(0) = 0	B2
Solution of B1 subject to initial condition B2 is:
T(n) = n(n+1) for n ≥ 0               2	B3

Verify closed-end solution - Substitute solution into recurrence formula to check that equality holds or use induction to prove.

B1 must hold for every n > 0:

Substitution	Induction
T(n) = n(n+1)     2 = (n2+n)/2 = (n2-n+2n)/2 = (n2-n)/2+2n/2 = (n-1)n + n     2 = T(n-1) + n	IH: T(n) = n(n+1)                     2 Base: B2 must hold for n=0: T(0) = 0(0+1) =     2 0 Show: T(n+1) = (n+1)(n+2)                                 2 T(n+1) = T(n+1-1) + (n + 1) = T(n) + n+1 Recurrence T(n) = T(n-1) + n   = n(n+1) + n+1        2 IH: T(n) = n(n+1)                     2   = (n2+n)/2+2(n+1)/2     = (n2+3n+2)/2     = (n+1)(n+2)            2 ∴

Particular solution to recurrence - a specific sequence that satisfies recurrence; B3 is a particular solution for B1 and B2.

General solution to recurrence - formula that specifies all sequences, typically includes arbitrary constants. A general solution for recurrence B1 is:

T(n) = c + n(n+1) for n ≥ 0
                   2

choosing different values for c gives all solutions to B1.

METHODS FOR SOLVING RECURRENCE RELATIONS

No universal method but common techniques for a variety of recurrences.

 

Forward substitution to find exact closed-end equation for T(n) - limited to simple recurrences

• Start with initial term(s) given by initial conditions, generate first few terms in hope of seeing a pattern that can be expressed by a closed-end formula

  Example

  T(n) = 2T(n-1)+1 for n > 1               B5

  T(1)=1                                             B6

  Generate

T(1) = 1 = 2¹-1

T(2) = 2T(2-1)+1 = 2T(1)+1 = 2*1+1 = 3 = 2²-1

T(3) = 2T(3-1)+1 = 2T(2)+1 = 2*3+1 = 7 = 2³-1

T(4) = 2T(4-1)+1 = 2T(3)+1 = 2*7+1 = 15 = 2⁴-1

Hope

Observe pattern that suggests from n=1, 2, 3, 4

T(n) = 2T(n-1)+1 = 2ⁿ-1

• Prove T(n) = 2ⁿ-1 correct by substitution or induction
  

Question 4.4

T(n) = T(n-1)+1 for n > 0               

T(0)=1                                        

Generate

T(1)=                                       

T(2)=                                       

T(3)=                                       

Closed form

Observe pattern T(n) =

Question 4.5 - Use substitution to prove T(n) = closed form

Question 4.6 - Use induction to prove T(n) = closed form

Backward substitution to find exact closed-end equation for T(n)

• express T(n-1) as a function of T(n-2)
  
• substitute result to give T(n) as a function of T(n-2)
  
• repeating for T(n-2) gives T(n) as function of T(n-3)
  
• hope to see a pattern to express T(n) as function of T(n-i) for i=1, 2, ...
  
• select i to make n-i reach the initial condition
  
• closed-end formula
  1. use standard summation formula from Appendix A will often lead to closed-end formula
     
  2. when lucky, get form similar to: T(n) = Base case + f(n), and can solve by substitution

   

Example - Backward substitution to find exact closed-end equation for T(n)

T(n) = T(n-1)+1 for n > 0               

T(1) = 1                                        

After 4 substitutions, observe that:

T(n) = T(n-4) + 4

T(5) = T(5-4) + 4       

       = T(1) + 4

       = 1 + 4

       = 5

After i substitutions, observe that:

T(n) = T(n-i) + i

Initial condition must hold: T(1) = T(n-i)

n-i = 1 ⇒ i=n-1

n=1: T(n-i) = T(n-(n-1)) = T(1-(1-1)) = T(1)

Closed-end equation

T(n) =  T(n-i) + i 

       = T(n -(n-1)) + n - 1

       = T(1) + n - 1

       = 1 + n - 1

       = n

Question 4.7

T(1) = 1              

T(n) = T(n-1) + 5  for n>1

a. What is T(2), T(3), T(4)?

T(n-1)=T(n-2)+5

T(n) = T(n-1) + 5 = [T(n-2)+5]+5

b. Use backward substitution to find the closed-end equation.

c. Verify the closed-end equation is correct for T(4).

 

Example - Backward substitution to find exact closed-end equation for T(n)

T(1) = 1

T(n) = 2T(n-1)+1 for n > 1

After 4 substitutions:

T(n) = 2⁴T(n-4)+2³+2²+2+1

T(5) = 2⁴T(5-4)+2³+2²+2+1       

       = 2⁴T(1)+2³+2²+2+1

       = 2⁴+2³+2²+2+1

After i substitutions, observe that:

T(n) = 2ⁱT(n-i) + 2^i-1 +... +2³+2²+2¹+2⁰

Initial condition must hold: T(1) = 2ⁱT(n-i)

n-i = 1 ⇒ i=n-1

n=1: 2ⁱT(n-i) = 2^n-1T(n-(n-1)) = 2^1-1T(1-(1-1)) = 2⁰T(1) = T(1)

Closed-end formula by exponential series:

From Appendix A.5, p. 1147

T(n) = 2ⁱT(n-i) + 2^i-1 + 2^i-2+ 2^i-3+...+2³+2²+2¹+2⁰

       = 2ⁱT(n-i) + 2ⁱ - 1         

       = 2^n-1T(n-(n-1)) + 2^n-1 - 1                   i = n-1

       = 2^n-1T(1) + 2^n-1 - 1                            T(1)=1

       = 2^n-1 + 2^n-1 - 1 

       = 2*2^n-1 - 1

            = 2ⁿ - 1

Proof - same as earlier forward substitution or induction

 

Example - Backward Substitution

T(0) = 0

T(n)=T(n-1) + n

T(n)	=T(n-1) + n	sub. T(n-1) = T((n-1)-1) + (n-1) = T(n-2) + n-1
	=T(n-2) + n-1 + n	sub. T(n-2) = T(n-3) + n-2
	=T(n-3) + n-2 + n-1 + n	sub. T(n-3) = T(n-4) + n-3
	=T(n-4) + n-3 + n-2 + n-1 + n

After 4 substitutions:

T(n) = T(n-4) + n-3 + n-2 + n-1 + n

T(4) = T(0) + 1 + 2 + 3 + 4 = 0 + 1 + 2 + 3 + 4

After i substitutions, observe that:

T(n) = T(n-i) + (n-i+1) + (n-i+2) + ... + (n-2) + (n-1) + n

Initial condition must hold: T(0) = T(n-i)

n-i = 0 ⇒ n=i

n=i=0: T(n-i) = T(n-n) = T(0)

Closed-end formula by standard summation for n=i

T(n) = T(n-n) + (n-n+1) + (n-n+2) + ... + (n-2) + (n-1) + n

T(n) = T(0) + 1 + 2 + ... + n = 0 + 1 + 2 + ... + n = n(n+1)/2

Proof:

T(n) = n(n+1)/2 correct by substitution or induction

Question 4.7.1 - Prove by induction the recurrence:

T(1) = 1              

T(n) = T(n-1) + 5  for n > 1

has the closed form:

T(n) = 5(n-1) + 1

IH:

Basis:

Show:

Proof:

 

COMMON RECURRENCE TYPES IN ALGORITHM ANALYSIS

• Decrease-by-one algorithms exploits relationship between instance of size n and smaller instance of size n-1.
  
• Decrease-by-a-constant factor algorithms reduce instance of size n to an instance of size n/b (b=2 for many such algorithms), solving the smaller instance recursively. If necessary, the solution of the smaller instance is combined to a solution of the given instance.
  
• Divide-and-conquer divides a given instance into smaller instances, solving each recursively. If necessary solutions to smaller instances are combined to give a solution to a given instance.

   

Decrease-by-one algorithms exploits relationship between instance of size n and smaller instance of size n-1.

For the recursive n! algorithm: int factorial (int n) {    if (n == 1) return 1;           // Cost = 1    return factorial (n-1) * n;    // Cost = T(n-1) + 1 } The running time, T(n),  can be defined as: T(1) = 1 T(n) = T(n-1) + 1 for all n > 1 where 1 is the running time for each execution of the factorial function. Solving the recurrence by recognizing the summation leads to closed-end formula: T(n) = T(1) + 1 + ... + 1 = 1 + 1 + ... + 1 = n

Typical form of recurrence equation, where f(n) is the time to reduce an instance to a smaller one is:

T(n) = T(n-1) + f(n)

Applying backward substitutions yields:

T(n) = T(n-1) + f(n)

       = T(n-2) + f(n-1) + f(n)

       = ...

       = T(0)+

For a specific function f(n), can usually be computed exactly or order of growth determined. As examples, for:

f(n)=1, = n

f(n)=lg n, ∈ Θ(n lg n)

f(n)=n^k, ∈ Θ(n^k+1)                      Consider: 4^k + 4^k + 4^k + 4^k = 4*4^k = 4^k+1        

The sum, , can also be approximated by formulas involving integrals.

 

Decrease-by-a-constant factor algorithms reduce instance of size n to an instance of size n/b (b=2 for many such algorithms), solving the smaller instance recursively. If necessary, the solution of the smaller instance is extended to a solution of the given instance.

For binary search: int binarySearch(int A[], int key, int low, int high) {      if (low > high) return -1;      int mid=(low+high)/2;                                                 if (key == A[mid]) return mid;      if(key > A[mid]) return binarySearch(A, key, mid+1, high);      else                    return binarySearch(A, key, low, mid-1); } Recurrence T(1) = 1                                                             Lines 1-4 T(n) = T(⌊n/2⌋) + 1 for n>1                             Lines 5-6, problem size now ⌊n/2⌋ Let n=2k (power of 2) and solve using backwards substitutions (see below) or other method. T(2k) = T(2k/2) + 1 = k+1 = lg 2k + 1 = lg n + 1

Typical form of recurrence equation, where f(n) is the time to reduce an instance to a smaller one is:

T(n) = T(n/b) + f(n)

where b>1 and f(n) is the time to reduce an instance to a smaller and to extend the solution to a solution of a larger instance.

Valid only for n=b^k for k=0, 1, 2, ..., that is n is a power of b.

Where n is not a power of b there is round-off, usually involving floor or ceiling functions.

Standard approach is solve for n=b^k first, then tweak to make valid for all n's.

For n=b^k, applying backward substitutions:

T(bk)	= T(bk-1) + f(bk)
	= T(bk-2) + f(bk-1) + f(bk)
	= ...
	= T(1) +

For a specific function f(x), can usually be computed exactly or order of growth determined.

Example of binary search, f(x) = 1:

= k = log_bn

Then for the binary search example:

T(1) = 1

T(n) = T(⌊n/2⌋) + 1 for n>1

Let n=2^k

Note that k=lg n

T(n) = T(2^k) = T(1) + = 1 + k = log₂n + 1 or lg n + 1

 

Example - Binary Search

Recurrence

T(1) = 1

T(n) = T(⌊n/2⌋) + 1 for n>1

Let n=2^k (power of 2) and solve using backwards substitutions.

T(2k)	= T(2k/2)+1	= T(2k-1)+1	sub. T(2k-1) = T(2k-1/2)+1
	= T(2k-1/2)+1+1	= T(2k-2)+1+1	sub. T(2k-2) = T(2k-2/2)+1
	= T(2k-2/2)+1+1+1	= T(2k-3)+1+1+1	sub. T(2k-3) = T(2k-3/2)+1
	= T(2k-3/2)+1+1+1+1	= T(2k-4)+1+1+1+1

After 4 substitutions:

 T(2^k) = T(2^k-4)+1+1+1+1

 T(2⁴) = T(2^4-4)+1+1+1+1 = T(1)+4 = 1 + 4 = 5

After i substitutions:

T(2^k) = T(2^k-i) + i

Need i so that T(2^k-i) = T(2⁰) = T(1):

i=k

Solution

Base case: k=0, n = 2^k = 2⁰ = 1

T(2⁰) = T(2^k-i) + i =  T(2^0-0) +0 = T(1) = 1

Closed-end equation by substitution

In general, for i=k

T(2^k) = T(2^k-i) + i

         = T(2⁰) + k

         = T(1) + k = k + 1

k + 1 = lg 2^k + 1                         since log₂ 2^k=k

                             = lg n + 1                           n=2^k

 

Show: T(n) = lg n + 1 correct by substitution or induction.

Let n=2^k (power of 2)

Substitution Show: T(2k)=T(2k/2) + 1  T(2k) = lg 2k + 1   = k + 1   =(k-1+1)+ 1   = (lg 2k-1 + 1) + 1   = T(2k-1) + 1   = T(2k/2) + 1

Induction Basis step T(20)=T(1) = 1 Inductive Hypothesis T(2k) = lg 2k + 1 = k + 1 Inductive step Show T(2k+1) = k + 2 T(2k+1) = T(2k+1)/2+1                   Recurrence            = T(2k+1-1) + 1            = T(2k) + 1            = (k+1) +1                           IH, T(2k) = k + 1 ∴        = k + 2            = lg 2k + 2

 

Divide-and-conquer divides a given instance into smaller instances, solving each recursively. If necessary solutions to smaller instances are combined to give a solution to a given instance.

Mergesort example void mergeSort( double A[] ) {     // A.length is power of 2    int n = A.length;    if (n > 1) {      double B[]=new double[n/2], C[]=new double[n/2];      copy( A[0..n/2-1], B);      copy( A[n/2, n-1, C);      mergeSort( B );      mergeSort( C );      merge( B, C, A );    } } Recurrence T(1) = b T(n) = T(n/2) + T(n/2) + cn for n>1 where: b is the time to solve a problem of size 1 n the problem size, in this case a power of 2. T(n/2) is the time to solve (mergeSort) half of the given problem (lines 7 and 8). cn is the time to divide the problem in half (lines 4-6) and combine solutions to each half (line 9). By backward substitution the recurrence yields: T(n) = 21T(n/21) + cn = 21[2T(n/22)+cn/2] + cn sub. T(n/21) = 2T(n/22)+cn/2   = 22T(n/22) + 2cn = 22[2T(n/23)+cn/22] + 2cn sub. T(n/22) = 2T(n/23)+cn/22   = 23T(n/23) + 3cn = 23[2T(n/24)+cn/23] + 3cn sub. T(n/23) = 2T(n/24)+cn/23   = 24T(n/24) + 4cn     Substituting i times yields (we're lucky, no summation!): T(n)= 2iT(n/2i) + icn Closed-end Initial condition must hold: T(1) = 2iT(n/2i) = 20T(n/20) 2i=n=1 when i=0 2i=n=2lg n or i=lg n.                       Closed-end solution: T(n) = 2iT(n/2i) + icn replace i=lg n   = 2lg nT(n/2lg n) + (lg n)cn     = nT(n/n) + (lg n)cn     = nT(1) + (lg n)cn     = nb + cn lg n   Proof: T(n) = nb + cn lg n Recurrence: T(1) = b T(n) = 2T(n/2) + cn for n>1 Basis: T(1) = 1b + c1 lg 1 = b + c*0 = b Inductive Hypothesis: T(n/2) = (n/2)b + c(n/2) lg (n/2) Show: T(n) = nb + cn lg n T(n) = 2T(n/2) + cn    Recurrence   = 2[ (n/2)b + c(n/2) lg (n/2) ] + cn    IH T(n/2) = (n/2)b + c(n/2) lg (n/2)   = nb + cn lg (n/2) + cn     = nb + cn ( lg n - lg 2) + cn     = nb + cn ( lg n - 1) + cn     = nb + cn lg n - cn + cn     = nb + cn lg n    ∴

General form of recurrence equation, where:

• n is the problem size
• b ≥ 2 the number of problem divisions
• n/b is the size of the smaller problem after division
• a ≥ 1 is the number of subproblem solutions
• f(n) is the time to divide an instance to a smaller ones and combine the solutions

T(n) = aT(n/b) + f(n)

Which, by backward substitution, we can derive:

where the order of growth solution T(n) depends upon the values of constants a and b and the order of growth of the function f(n).

Under certain assumptions about f(n), the above can be simplified to get explicit results about the order of growth of T(n). That will be examined when considering the Master Theorem.