If you want to make money online : Register now

Solve Recurrence Relation

, , No Comments
Problem Detail: 

I'm trying to solve the following recurrence relation. I've gotten through two iterations, but I don't see any pattern. I would appreciate any help with this.

$T(1)=1$

$T(n)=6\ T(n/6)\ +\ 2n\ +\ 3$

I've manually ran through two iterations and found the following:

$T(n/6)= 36T(n/36)+14n+21$

$T(n/36)=216(n/216)+86n+129$

The pattern that I see is:

$T(n) = 6^k(n/(6^k))+ (I\ can't\ determine\ the\ pattern\ of\ these\ terms)$

Asked By : Rusty
Answered By : tenCupMaximum

Hint:

$$T(n)=6\ T(n/6)\ +\ 2n\ +\ 3$$

$$T(n)=6\ (6\ T(n/6^2)\ +\ 2(n/6)\ +\ 3)\ +\ 2n\ +\ 3$$

$$T(n)=6\ (6\ (6\ T(n/6^3)\ +\ 2(n/6^2)\ +\ 3)\ +\ 2(n/6)\ +\ 3)\ +\ 2n\ +\ 3$$

Distribute the 6's.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57068

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback