Analysis of Algorithms : An Active Learning Approach

1.6 RECURRENCE RELATIONS 33

The second is used if the direct solution is applied for a larger number of cases:

These forms are equivalent. We can convert from the second form to the first
by just listing those values for which we have the direct answer. This means
that the second recurrence relation above could also be given as

Consider the following recurrence relation:

We will want to substitute an equivalent value for T(n
2) back into the first
equation. To do so, we replace every n in the first equation with n
2, giving:

But now we can see when this substitution is done, we will still have T(n
4)
to eliminate. If you think ahead, you will realize that there will be a series of
these values that we will need. As a first step, we create a set of these equations
for successively smaller values:

Tn()^4 if n≤^4

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





=

Tn()= 4 Tn()⁄ 2 – 1

T() 4 = 4

T() 3 = 4

T() 2 = 4

T() 1 = 4

Tn()= 2 Tn()– 2 – 15

T() 2 = 40

T() 1 = 40

Tn()– 2 = 2 Tn()– 2 – 2 – 15

= 2 Tn()– 4 – 15

Tn()– 2 = 2 Tn()– 4 – 15

Tn()– 4 = 2 Tn()– 6 – 15

Tn()– 6 = 2 Tn()– 8 – 15

Tn()– 8 = 2 Tn()– 10 – 15

Tn()– 10 = 2 Tn()– 12 – 15