# Solving Recurrences Using Master Method [duplicate]

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.

## marked as duplicate by Raphael♦ algorithms StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Sep 18 '18 at 9:23

• In your third problem, it should be $\frac{n + 3}{3}$, not $\frac{4n}{3}$. – Gokul Sep 18 '18 at 2:28
• 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. – Raphael Sep 18 '18 at 9:24
• @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. – Jerry M. 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.

• 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. – Raphael Sep 18 '18 at 9:25