2
$\begingroup$

So I'm working through my homework, and applying the Master Theorem pretty easily, then my prof throws me a curve ball

$T(n) = 4T(3n/4) + n^4$

Now I used my usual steps of listing out what A, B, and f(n) is:

a = 4
b = 3/4
$f(n) = n^4$

but $\log_{3/4} 4$ does not work out to be a nice a number to fiddle around with in the masters theorem. So is this the right path? Or is there some special rule that applies when b = 3/4?

  • 0
    So i should just go ahead with using 3/4 as my b?2012-09-25

1 Answers 1

0

When using the Master Theorem $b$ symbols the number the $n$ that n is divided by ($\frac{n}{b}$),
Thus, your $b$ should be $\frac{4}{3}$ since $\frac{n}{\frac{4}{3}} = \frac{3n}{4}$.

The $b$ you chose symbols the number that $n$ is multiplied by, and we are not interested in this number at all.