Inhomogeneous Recurrences

 

a₀t_n  +  a₁t_n-1 + a₂t_n-2  +  a_kt_n-k  =   bⁿ p(n)

where b is a constant and p(n) is a polynomial in n of degree d. 

 

General solution is obtained by solving the following equation:

            (a₀x^k  +  a₁x^k-1  +  a₂x^k-2  + … + a_k) (x-b)^d+1 = 0

 

Example:                    

   Function Hanoi(m,i,j)

   // move m(smallest) rings from rod i to rod j by way of rod 6-i-j.

       if m>0

               { Hanoi(m-1,i,6-i-j);

                  write “move ring “, m, “ from rod “, i, “ to rod “, j;

                  Hanoi(m-1,6-i-j,j);

               }

               // end of function Hanoi

 

    Recurrence Relation

 

        t_m   = a if m=0

              = 2t_m-1+b otherwise.

 

         So, (x-2)= b =1^m * b . 

So b=1 and p(m)= b which is of degree 0 (d=0).

            (x-2)(x-1)¹  = 0.

             x=2 and x=1

            General solution:    t_m = c₁*2^m + c₂*1^m  =  c₁*2^m + c₂                     

            We find that

1.                                                                  c₁+c₂      =a       (which is t₀)

2.                                                                  2*c₁+c₂=2a+b (which is t₁)

3.                                                                  c₁=  a+b

4.                                                                  c₂=  -b           

            So, t_m = (a+b)*2^m -b  and O(t_m) =  2^m                     

 

Using the ordinary generating function.

 

            t₀    = a

            t_m   = 2t_m-1 + b , for m>=1

 

            inf.               inf.                  inf.

S  t_m x^m  = 2 S  t_m-1 x^m   + b S x^m               

            m=1             m=1                m=1 

           

            G(x) - t₀ =   G(x) - a  = 2xG(x) + bx/(1-x)

            G(x) = a/(1-2x)  + bx/((1-x)(1-2x))

            G(x) = a/(1-2x)  + b(1/(1-2x)-1/(1-x))

                     = (a+b)/(1-2x)  - b/(1-x)  

            So,   t_m = (a+b)*2^m – b*1^m, the same result.

 

In general, if we have recurrences of the form:

  a₀t_n  +  a₁t_n-1 + a₂t_n-2  +  a_kt_n-k  =  b₁ⁿ p₁(n) + b₂ⁿ p₂(n) + … +  b_mⁿ p_m(n)

where polynomials, p(n), on RHS are of degree d1, d2, and dm,

respectively,                            

we can solve this by solving the following characteristic polynomial:

   (a₀ x^k  + a₁ x^k-1  + … + a_k) (x-b₁) ^d1+1 (x-b₂) ^d2+1 …  (x-b_m) ^dm+1                   

 

Example:

T_n    =  0 if n=0

            2 T_{n-1  +} n + 2ⁿ   if n>=1             

            So,  T₀ = 0,  T₁ = 3,  T₂  =  12 and  T₃  = 35, which we may need later.

 

And, then the characteristic polynomial turns out to be:

(x-2) (x-1)² (x-2) =  (x-2)² (x-1)²   =  0

General solution is:  T_m  =  c₁2^m  + c₂ m2^m  + c₃1^m  +  c₄ m1^m   

Now, to get the particular solution, we need to find particular values of c’s that

Satisfy the first four values of T’s,   T₀ ,  T₁ , T₂ , and  T₃.    

 T₀ =  0  =   c₁  +  c₃  

and  c₁  =  -c₃.                                      (a)

 T₁ =  3  =  2c₁  + 2c₂  + c₃  +  c₄   =  -2c₃  + 2c₂  + c₃  +  c₄,

              c₃  = 2c₂  + c₄ - 3                                           (b)

T₂ =  12 =  4c₁  + 8c₂  + c₃  +  2c₄                

T₃ =  35 =  8c₁  + 24c₂  + c₃  + 3c₄          

From (a), (b) and T₂, we have   2c₂  -  c₄ = 3.

From (a), (b) and T_{3,  we} have 10c₂  - 4c₄  = 14.

From the last two equations, we get   c₄ = -1,  c₂ = 1, c₃ = -2 and c₁ =2.  

 So,  the particular solution is: 

T_m  =  2*2^m  + m2^m  - 2*1^m  - m1^m   

      =  2^m+1    + m2^m  - m - 2

and  O(T_m) = m2^m.

 

Change of Variables: Useful especially when the parameter changes

by a geometric progression like halving

 

Example1:

            T(n) = 4T(n/2) + n²   where n>=2 is a power of 2.

            Let n = 2ⁱ  and  t_i  = T(n) = T(2ⁱ)  and T(n/2) = T(2^i-1) = t_i-1

So, the recurrence becomes:   

                        t_i  = 4t_i-1  + (2ⁱ)²  = 4t_i-1  + 4ⁱ 

            From above, we get  t_m  =  a*4^m  + b*m4^m   

           The two above arbitrary constants a and b can be solved

from two initial conditions  t₀ and t₁.

           And, from n = 2ⁱ  and  t_i  = T(n) = T(2ⁱ), we get

                       T(n) = a n²+ bn² log n      

 

Example2: (Simpler one by Iteration) 

            T(n) = T(n/2) + n   where n>=2 is a power of 2 and T(1)=c.

            Just like Example1 above, we can use “Change of variables” method.

            But, in this case, we can just use an iteration method due to the

            simplicity of recurrence relation.

           Since n is a power of 2, n=2^k   for some integer k.

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

                   =  2^k + 2^k-1 + 2^k-2 + 2^k-3 + T(2^k-4) = 2^k + 2^k-1 + 2^k-2 + 2^k-3 + …+ 2¹ + T(2⁰)  

        =  2^k + 2^k-1 + 2^k-2 + 2^k-3 + …+ 2¹ + T(1)

        =  2^k+1  - 2 + c =  2n - 2 + c

So,  T(n) = O(n) and also Ω(n).     

It is noteworthy that due to the fact that T(n) is monotonically non-decreasing

the above result, T(n) = O(n) and also Ω(n), holds even when n is not

a power of 2.

How would you show that T(n) is monotonically non-decreasing, that is,

T(n) >= T(n-1) for every n>=2???               

 

 Ω Notation: (Lower Bounds)

 Definition:

 f(n) is in Ω(g(n)) if and only if  f(n) >= c₁ (g(n)) for  all n>= c₂. 

 

 This is exactly analogous to the definition of O(n) as  

 f(n) is in O(g(n)) if and only if  f(n) <= c₁ (g(n)) for  all n>= c₂.   

 

Main Recurrence Theorem.

Let a, b, and k be integers such that a>=1, b>=2 and k>=0.

In the following, n/b denotes either the floor function or the ceiling function.

In the case of the floor function, the initial condition T(0)=u is given.

And, in the case of the ceiling function, the initial condition T(1)=u  is given.

If  T(n) <= aT(n/b) + f(n) and  f(n)=O(n^k ) ---Rec.1.1

then  T(n) = O(n^k )          if a< b^k  ,

                 = O(n^k log n)  if a= b^k  ,

                 = O(n ^{log b a} )   if a >b^k          

Note that if Rec.1.1 above is an equality (instead of an inquality) then the Ө-notation will

replace the O-notation.

 

Example-3:

 T(n) <= T(floor(n,2)) + T(ceiling(n,2)) + n² .

 Assume that T(n) is nondecreasing.

 Since T(n) is nondecreasing,  T(floor(n,2)) <= T(ceiling(n,2)).

 So, T(n) <= 2T(ceiling(n,2)) + n².

 Applying the above Theorem with a = b = k = 2, we have T(n) = O(n² ) as a < b^k .