0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\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 Sep 27 '17 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 Sep 27 '17 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 Sep 27 '17 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 Sep 27 '17 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 Sep 27 '17 at 22:08

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.