Solving Recurrences Using Master Method [duplicate]

Question

This question already has an answer here:

• Solving or approximating recurrence relations for sequences of numbers 11 answers

Using the Master Method, I need to prove (True, or False and why) the following (3) recurrences:

1. $T(n) = 3T(\frac{n}{2}) + n = \Theta(n\ln(n))$

2. $T(n) = T(\sqrt{n}) + 1 = \Theta(n^2)$

3. $T(n) = 2T(\frac{n}{3} + 1) + n = \Theta(n\ln(n))$

I understand the Master Method (I think, largely from: https://stackoverflow.com/questions/13430256/understanding-master-theorem) and from my CLRS Text.

Problem 1: Would be case 1, but I don't understand how to use it in this case? What would my ɛ be in this case to perform the logarithmic function? I know that ultimately, my time complexity will be $\Theta(n^{1.58})$, but I don't know how to prove that without knowing ɛ

Problem 2: I have no idea.

Problem 3: I believe this is false, because this can be rewritten as $T(n) = 2T(\frac{4n}{3}) + n$, which would be Case 2, and therefore give me a time complexity of $\Theta(ln(n))$.

This is my first time taking anything this granular with algorithms, and despite reading CLRS and looking at videos online, I am a bit lost, and would appreciate any help. Thanks in advance.

Answer 1

1) $T(n) = 3T(\frac{n}{2}) + n \in \Theta(n\ln(n))$

a = 3, b= 2 and f(n) = $\Theta(n)$

$n^{\log_b a} = n^{\log_2 3} > n^{\log_2 2} = n = f(n) \therefore f(n) \in \Theta(n^{\log_2 3})$

(Case 1) Proved False

2) It is not in the Master Theorem format $T(n) = aT(\frac{n}{b}) + f(n) \therefore$

It is not possible to say if the statement is true or false using the Master Theorem

3) $T(n) = 2T(\frac{n}{3}+1) + n = 2T(\frac{n+3}{3}) + n \in \Theta(n\ln(n))$

a = 2, b= 3 and f(n) = $\Theta(n)$

$n^{\log_b a} = n^{\log_3 2} < n^{\log_3 3} = n = f(n) \therefore$

Case 3.

Now we could check if it is the case that $T(n) \in \Theta(f(n))$, but we don't need to, because the only way it would be $\Theta(n\log n)$ was if it was case 2.