I just took a quiz for an algorithms class that I didn't do so well on. It was on the master theorem. Unfortunately the professor refuses to supply answers or even tell me what I got wrong, so I was hoping someone could help me understand what I did wrong for the following problems. In each problem I am supposed to find the asymptotic solution (using $\Theta(n)$) notation for each recurrence:
$T(n) = 12T(\frac{n}{12}) + 8n$
$T(n) = 12T(\frac{n}{24}) + 24n$
$T(n) = 12T(\frac{n}{6}) + 2n$
First of all the only examples or homework we had done with these where $f(n)$ was some function that didn't have a constant in front of it. I assumed that for all of these problems I would be able to drop the constant in $f(n)$ so that $f(n) = n$
$a = 12$, $b = 12$, $f(n) = n$ so $n^{\log_{12}12} = n = f(n)$. therefore we can use case 2 to get $\Theta(n\log n)$
$a = 12$, $b = 24$, $f(n) = n$ so $n^{\log_{24} 12} = n^{0.5} = \sqrt{n}$. Using case 1 of the master theorem we get $\Theta(\sqrt{n})$
$a = 12$, $b = 6$, $f(n) = n$. so $n^{\log_{6} 12} = n^{1.5}$ Note that we were not allowed calculators so the 1.5 was just me guessing. And since this is larger then $f(n)$ we can use case 3 of the master theorem to get $\Theta(n^2)$.
Your calculation of log is off.
$log_{24}12 \ne 0.5$ and $log_6 12 \ne 1.5$
2) a = 12, b = 24, $p =log_{24} 12 < 1$, $f(n) = n = \Omega(n)$, and $ c= 1 > log_{24}12$, it is the case 3 of the master theorem.
3) a = 12, b = 6, $p = log_6 12 > 1$, $f(n) = n = O(n)$, where $c = 1 < log_6 12$, this is the case 1.