Analysis of Algorithms : An Active Learning Approach

1.6 RECURRENCE RELATIONS 35

indicates that we would have substituted five times, would have six terms

based on 
15, and would have 2^6 for the coefficient of T(2). If you look

closely at the last equation and substitute 14 in for n, you will see that this is

exactly what we have.

What if n is an odd number? Will these formulas still work? Let’s consider

ann value of 13. In the above equation, the only thing that would change is

thatT would have a value of 1 instead of 2, but by our equations, n / 2 
 1 is

5 (not 6) when n is 13. For odd n, we will use n / 2 instead of n / 2 
 1. We

will have two cases in our answer.

Now, applying Equation 1.17, for an even value of n we get

and, if n is odd, we get

Consider another recurrence relation:

We will proceed in the same way as we did in the previous example. We first

substitute in a set of values for n, only in this case, because n is being divided

Tn() 2 ()n⁄^2 –^1 T() 2 15 2 i ifn is even
i=0

()n⁄ 2 – 1

= – ∑ Tn() 2 n⁄^2 T() 1 15 2 i ifn is odd

i=0

n⁄ 2

= – ∑

Tn() 2 ()n⁄^2 –^1 * 40 15 2 i ifn is even
i=0

()n⁄ 2 – 1

= – ∑ Tn() 2 n⁄^2 * 40 15 2 i ifn is odd

i=0

n⁄ 2

= – ∑

Tn()= 2 ()n⁄^2 –^1 * 40 15– * () 2 n⁄^2 – 1

= 2 n⁄^2 * 20 2– n⁄^2 * 15 15+

= 2 n⁄^2 ()20 15– + 15

= 2 n⁄^2 * 515 +

Tn()= 2 n⁄^2 * 40 15– * () 2 ()n⁄^2 +^1 – 1

= 2 n⁄^2 * 40 2– n⁄^2 * 30 + 15

= 2 n⁄^2 ()40 30– + 15

= 2 n⁄^2 * 10 15+

Tn()^5 if n≤^4

^4 Tn()⁄^2 –^1 otherwise





=