Recurrence Relation

 

Recurrence Relation

A recurrence is an equation or inequality that describes a function in terms of its values on smaller inputs. To solve a Recurrence Relation means to obtain a function defined on the natural numbers that satisfy the recurrence.

For Example, the Worst Case Running Time T(n) of the MERGE SORT Procedures is described by the recurrence.

T (n) = θ (1) if n=1
 2TDAA Recurrence Relation + θ (n) if n>1

There are four methods for solving Recurrence:

  1. Substitution Method
  2. Iteration Method
  3. Recursion Tree Method
  4. Master Method

1. Substitution Method:

The Substitution Method Consists of two main steps:

  1. Guess the Solution.
  2. Use the mathematical induction to find the boundary condition and shows that the guess is correct.

For Example1 Solve the equation by Substitution Method.

	T (n) = TDAA Recurrence Relation + n

We have to show that it is asymptotically bound by O (log n).

Solution:

For T (n) = O (log n)

We have to show that for some constant c

  1. T (n) ≤c logn.  

Put this in given Recurrence Equation.

	T (n) ≤c logDAA Recurrence Relation+ 1
			≤c logDAA Recurrence Relation+ 1 = c logn-clog2 2+1
			≤c logn for c≥1
Thus T (n) =O logn.

Example2 Consider the Recurrence

T (n) = 2TDAA Recurrence Relation+ n n>1

Find an Asymptotic bound on T.

Solution:

We guess the solution is O (n (logn)).Thus for constant 'c'.
 T (n) ≤c n logn
Put this in given Recurrence Equation.
Now,
  T (n) ≤2cDAA Recurrence Relationlog DAA Recurrence Relation+n
      ≤cnlogn-cnlog2+n
      =cn logn-n (clog2-1)
      ≤cn logn for (c≥1)
Thus T (n) = O (n logn).

2. Iteration Methods

It means to expand the recurrence and express it as a summation of terms of n and initial condition.

Example1: Consider the Recurrence

  1. T (n) = 1  if n=1  
  2.       = 2T (n-1) if n>1  

Solution:

  
T (n) = 2T (n-1)
      = 2[2T (n-2)] = 22T (n-2)
      = 4[2T (n-3)] = 23T (n-3)
      = 8[2T (n-4)] = 24T (n-4)   (Eq.1)

Repeat the procedure for i times

T (n) = 2i T (n-i)
Put n-i=1 or i= n-1 in    (Eq.1)
T (n) = 2n-1 T (1)
      = 2n-1 .1    {T (1) =1 .....given}
      = 2n-1

Example2: Consider the Recurrence

  1. T (n) = T (n-1) +1 and T (1) =  θ (1).  

Solution:

 T (n) = T (n-1) +1
       = (T (n-2) +1) +1 = (T (n-3) +1) +1+1
       = T (n-4) +4 = T (n-5) +1+4
       = T (n-5) +5= T (n-k) + k
Where k = n-1
   T (n-k) = T (1) = θ (1)
   T (n) = θ (1) + (n-1) = 1+n-1=n= θ (n).

Comments

Post a Comment

Popular posts from this blog

Recursion Method

Image
  Recursion Tree Method 1. Recursion Tree Method is a pictorial representation of an iteration method which is in the form of a tree where at each level nodes are expanded. 2. In general, we consider the second term in recurrence as root. 3. It is useful when the divide & Conquer algorithm is used. 4. It is sometimes difficult to come up with a good guess. In Recursion tree, each root and child represents the cost of a single subproblem. 5. We sum the costs within each of the levels of the tree to obtain a set of pre-level costs and then sum all pre-level costs to determine the total cost of all levels of the recursion. 6. A Recursion Tree is best used to generate a good guess, which can be verified by the Substitution Method. Example 1 Consider T (n) = 2T + n 2 We have to obtain the asymptotic bound using recursion tree method. Solution:  The Recursion tree for the above recurrence is Example 2:  Consider the following recurrence T (n) = 4T +n Obtain the asymptotic bound usi
Read more

Substitution Method

Image
The Substitution Method Consists of two main steps: Guess the Solution. Use the mathematical induction to find the boundary condition and shows that the guess is correct. For Example1  Solve the equation by Substitution Method. T (n) = T + n We have to show that it is asymptotically bound by O (log n). Solution: For T (n) = O (log n) We have to show that for some constant c T (n) ≤c logn.   Put this in given Recurrence Equation. T (n) ≤c log + 1 ≤c log + 1 = c logn-clog 2 2+1 ≤c logn for c≥1 Thus T (n) =O logn . Example2  Consider the Recurrence T (n) = 2T + n n>1 Find an Asymptotic bound on T. Solution: We guess the solution is O (n (logn)).Thus for constant 'c'. T (n) ≤c n logn Put this in given Recurrence Equation. Now, T (n) ≤2c log +n ≤cnlogn-cnlog2+n =cn logn-n (clog2-1) ≤cn logn for (c≥1) Thus T (n) = O (n logn) . 2. Iteration Methods It means to expand the recurrence and express it as a summation of terms of n and initial condition. Exa
Read more