Solve the recurrence relations using the guess and check method

Noomy 0
Viewed 40

I've got a problem where I forgot how to do recurrence relations and I'm not really sure what the guess and check method is. Does anyone know how to solve them using that method and if so a nice explanation would be appreciated.

2.  Solve the following recurrence relation from guess and check method.

a.  T(n) = T(n/2) + T(n/3) + T(n/10) + c n  where c is a constant.

T(small number) = another small number.

b.  T(n) = T(n/2) + T(n/3) + T(n/4) + T(n/5) + d n  where d is a constant

T(small number) = another small number.
recurrence complexity-theory algorithm
1 Answers

The guess method works by figuring out a possible answer and testing it. For a., if the function T does not grow too slowly, the T on the left could follow the last, linear term. So we try T(n) = an.

an = an/2 + an/3 + an/10 + cn

which indeed gives the solution

a = 15c.

For b., this fails as we get a negative coefficient, and we are a little stuck. We can try a larger power of n to increase the growth, and try an^α:

an^α = an^α/2^α + an^α/3^α + an^α/4^α + an^α/5^α + cn

After simplification,

1 = 1/2^α + 1/3^α + 1/4^α + 1/5^α + c/a n^(1-α)

Now by numerical resolution, we observe that with α = 1.2348, we have

0 ~ c/a n^(1-α)

which gives us an asymptotic solution.

Yves Daoust0
Related