# Trying to solve the recurrence relation by comparing 3 cases of master theorem

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.

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.

• 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 – Dan Sep 27 '17 at 20:10
• @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. – Raphael Sep 27 '17 at 20:19
• @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. – Raphael Sep 27 '17 at 20:20
• 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? – Dan Sep 27 '17 at 21:48
• @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. – Raphael Sep 27 '17 at 22:08