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.

  • $\begingroup$ In your third problem, it should be $\frac{n + 3}{3}$, not $\frac{4n}{3}$. $\endgroup$ – Gokul Sep 18 '18 at 2:28
  • $\begingroup$ Please ask only one question per post. While I think that all problems can be solved by carefully reading our reference question, there may be a more focused question for 1. in here (where you include an attempt). If you edit to focus on that, I'd be ready to reopen. $\endgroup$ – Raphael Sep 18 '18 at 9:24
  • 1
    $\begingroup$ @Raphael thank you for the explanation. I was definitely incorrect with how I worded the question. I have now read the forum rules more closely, and checked out the post you attached, and found some answers (and more questions :)). Thank you. $\endgroup$ – wundermahn Sep 19 '18 at 23:30

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.

  • $\begingroup$ Welcome, and thanks for taking the time to write an answer! Note that we have compiled a list of reference questions in order to avoid providing essentially the same answers over and over again; that time can be used on tougher questions! You may want to cross-reference with that list and save yourself some time in the future. $\endgroup$ – Raphael Sep 18 '18 at 9:25

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