# Solve Recurrence Relation [duplicate]

This question already has an answer here:

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)$

## marked as duplicate by David Richerby, vonbrand, Evil, Discrete lizard♦, Yuval FilmusMay 19 '18 at 10:56

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael May 5 '16 at 11:35

## 2 Answers

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.

• as a general rule you'll want to expand your stuff out like this so you can see the pattern more easily, rather than grouping over and again – quietContest May 5 '16 at 3:03

It's probably easier solving this using the Master Theorem.

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

So in this case A=6, B=6, and D=1 because f(n) = 2n + 3 and 2n^1 + 3 = 2n + 3

We of course assume the base case is a constant such that T(1) = C

So we can easily see that the answer for this is T ( n ) = Θ ( n log n ) , since A is equal to B to the power of D.

We can see that is true just by plugging in the values

= A = B^D

= 6 = 6^1

= 2 > 1 (which is always true)

This guy on YouTube has a very nice video explaining how to solve recurrences using the Master theorem, I will leave the link here.