Using the Master Method, I need to prove (True, or False and why) the following (3) recurrences:
$T(n) = 3T(\frac{n}{2}) + n = \Theta(n\ln(n))$
$T(n) = T(\sqrt{n}) + 1 = \Theta(n^2)$
$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.