The following recurrence relation,

$$T(n)=16T(\frac{n}{4}) + n^2$$

has been given to me to be solved via the Master Theorem. I'm pretty sure this is a case 2 situation, since

$$\log_4{16} = 2$$ and

$$\log_n{n^2} = 2$$

Where $b = 4$, $a = 16$, and $c = 2$, such that $f(n) = n^c$

What I'm not sure about is the end runtime complexity.

What I've come up with so far is

$$T(n) = \theta(n^2log_2{n})$$

...since the Master Theorem states that, for case 2 situations, $f(n)$ must be within the set of $O(n^clog^kn)$, where $k$ is some constant in which $k \ge 0$.

My reasoning was to substitute 0 for $k$, which led to $\log_2^1{n}$ in the result, as the result requires that $T(n) = \theta(n^clog_2^{k+1}{n})$.

In a nutshell, while I know the first portion of the analysis is correct, and that this is a case 2 situation, am I correct in the reasoning behind the logarithmic portion in the ending runtime analysis?

  • 1
    $\begingroup$ Either your proof works, or there is some gap. In both cases, you should be able to find out yourself. We have a policy of not grading homework on this site. $\endgroup$ – Yuval Filmus Apr 24 '14 at 0:28
  • $\begingroup$ Does our reference question help? @YuvalFilmus, I think this question contains a (just barely) specific enough question about the attempt to be allowable. $\endgroup$ – Raphael Apr 24 '14 at 6:14
  • 1
    $\begingroup$ "What I'm not sure about is the end runtime complexity." A recurrence is just a way of defining a function: it has nothing to do with runtime complexity per se, since that function could be used to measure anything at all. It's a bit like saying "I'm trying to work out what the total distance is in 753+3858" -- the numbers in the sum could stand for anything. $\endgroup$ – David Richerby Apr 24 '14 at 8:03

The Master theorem (roughly) states that in case two,

$\qquad\displaystyle f \in \Theta\left( n^{\log_b a} \log^{k} n \right) \implies T \in \Theta\left( n^{\log_b a} \log^{k+1} n \right)$.

That is, once you have identified the recurrence as case two by finding $k \geq 0$ so that $f$ is in this $\Theta$-class, the theorem automagically spits out the final result -- no further reasoning on your part necessary.

To be specific, in your case $a=16$, $b=4$ and $f : n \mapsto n^2$; therefore, $f \in \Theta\bigl( n^{\log_b a} \log^{k} n \bigr) = \Theta\bigl( n^2 \log^{k} n \bigr)$ with $k=0$ and you get

$\qquad\displaystyle T \in \Theta(n^2 \log n)$.

Two comments:

  • You use base $2$ for the logarithm in the final result. It should be $b=4$ (check the proof of the Master theorem) but it luckily does not matter; all logarithms share the same $\Theta$-class.
  • You talk about "runtime analysis"; this is not specific to runtime functions, and the recurrence at hand is unlikely to accurately describe the runtime of any algorithm. See also here.
| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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