I am trying to understand how the master theorem is invoked on the following recurrence relation:

$$ T(n) = \sqrt{6006} T(n/2) + n^{\sqrt{6006}}. $$

So basically, I found the following source where they have Master theorem definition defined.

I found the similar solution (See the Link #1 in the comment below) where they are trying to solve the same problem (Problem #c). I

In the solution, they have mentioned the following :

We have :

n0.5logb(a) = nlogb(6006)1/2

= n0.5log2(6006)1/2

and so on and so forth. I am not able to understand how they compared the results with the given equation.


1 Answer 1


You determine $a$, $b$, and $f$ using pattern matching.

The Master theorem applies for recurrences of the form

$\qquad\displaystyle T(n) = a T(n/b) + f(n)$;

you have

$\qquad\displaystyle T(n) = \sqrt{6006} \cdot T(n/2) + n^{\sqrt{6006}}$.

Just by comparing the two formulae, you determine that

$\qquad\begin{align*} a &= \sqrt{6006},\\ b &= 2, \quad\text{and} \\ f &= n \mapsto n^{\sqrt{6006}}. \end{align*}$

Now you go through the three cases and check which applies (if any). See also here.

  • $\begingroup$ Thanks. Looking at the 3 cases, it looks like it closely matches with the theta one which is case #2. $\quad \displaystyle f \in \Theta\left( n^{\log_b a} \log^{k} n \right)$ . I am wondering, do I need to substitute each values of a and b into the case 2 and then come up with the final answer which is T(n) = Theta (n ^(6006)^1/2) ? I didn't quite understand how this final answer is achieved $\endgroup$
    – Dan
    Commented Sep 27, 2017 at 20:10
  • $\begingroup$ @Dan It seems to me you need to learn how to read mathematics. Let me recommend Book of Proof. But yes, that's toughly how it works. $\endgroup$
    – Raphael
    Commented Sep 27, 2017 at 20:19
  • $\begingroup$ @Dan That said, how is $n^x \in \Theta(n^{\log_2 x} \cdot \log^k n)$ for any $k$ (with $x > 0$)? Because that's what you're claiming. You may need to check this out, too. $\endgroup$
    – Raphael
    Commented Sep 27, 2017 at 20:20
  • $\begingroup$ Thanks again. I claimed case #2 and the solution claims case #3. I am wondering whether there is correct answer or wrong answer to such type of questions because we have to roughly figure out the closest match. Different people could claim different anaswers? $\endgroup$
    – Dan
    Commented Sep 27, 2017 at 21:48
  • $\begingroup$ @Dan "because we have to roughly figure out the closest match" -- No. This is precise mathematics. At most one case can match. (For some recurrences, no case matches.) As I tried to hint, you're wrong. Try to understand why, using the resources I linked. $\endgroup$
    – Raphael
    Commented Sep 27, 2017 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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