0
$\begingroup$

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

$\endgroup$

marked as duplicate by David Richerby, vonbrand, Evil, Discrete lizard, Yuval Filmus May 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.

  • 1
    $\begingroup$ 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! $\endgroup$ – Raphael May 5 '16 at 11:35
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – quietContest May 5 '16 at 3:03
0
$\begingroup$

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

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

enter image description here

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.