Analysis of Algorithms : An Active Learning Approach

1.6 RECURRENCE RELATIONS 37

have the direct case specified for n≤ 4, we can stop when we get to

. Putting this together we get

Using the value for the direct case, and Equation 1.18, we get

As you can see, the closed form of a recurrence relation may not be simple

or neat, however, it does eliminate the recursive “call” so that we can quickly

compare equations and determine their order.

1.6.1
Put the following recurrence relations into closed form.

1.

2.

3.

4.

T() 4 =Tn()⁄ 2 lgn–^2

Tn() 4 lgn–^2 T() 4 4 i

i=0

lgn– 3

= – ∑

Tn() 4 lgn–^2 * 5 4

lgn– (^2) – 1
41 –
= –-----------------------
Tn() 4 lgn–^2 5 4
lgn– (^2) – 1
= –---------------------- 3 -
Tn()^15 ^4
lgn– (^2) – 4 lgn– (^2) + 1
= -------------------------------------------------------- 3
Tn()^4
lgn– (^2) ()15 1– + 1
= ------------------------------------------- 3
Tn()^4
lgn– 2

• 14 1+
  3
  = ------------------------------------
  ■1.6.1 EXERCISES
  Tn()= 3 Tn()– 1 – 15
   T()^1 =^8
  
  Tn()=Tn()– 1 +n– 1
   T()^1 =^3
  
  Tn()= 6 Tn()⁄ 6 ++ 2 n 3
   T()^1 =^1
   forn a power of 6
  Tn()= 4 Tn()⁄ 3 + 2 n– 1
   T()^1 =^2
   forn a power of 3