0
$\begingroup$

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:

  1. $T(n) = 12T(\frac{n}{12}) + 8n$

  2. $T(n) = 12T(\frac{n}{24}) + 24n$

  3. $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$

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

  2. $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})$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Like I said it was a quiz (we only had 8 minutes) and I was not allowed to use a calculator. I realize this may have been wrong but from what I understand it should give me roughly those answers since it's a bound? $\endgroup$
    – Alex
    Feb 10, 2016 at 3:58
  • $\begingroup$ 2) is case 3? 3) is case 1? you have no need to evaluate log. $\endgroup$
    – runaround
    Feb 10, 2016 at 4:08
  • $\begingroup$ I apologize for not understanding.. the way my teacher taught it was that I would need to evaluate log in order to see if the term n^e was polynomially smaller, larger or equal to f(n) $\endgroup$
    – Alex
    Feb 10, 2016 at 4:15
  • $\begingroup$ Everyone make mistakes. Keep in mind, if it is 8 minutes quiz, the professor didn't expect you to evaluate the log. If you did it, something is wrong. $\endgroup$
    – runaround
    Feb 10, 2016 at 4:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .