Master Theorem: How to find the value of b in this recurrence relation - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T13:49:22Z https://cs.stackexchange.com/feeds/question/63981 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/63981 3 Master Theorem: How to find the value of b in this recurrence relation EvaD https://cs.stackexchange.com/users/58999 2016-09-28T00:11:00Z 2016-09-29T17:52:18Z <p>The master theorem is used with recurrences of the form <code>T(n) = aT(n/b) + f(n)</code> where a >=1 and b > 1, in which case the value of b can be easily seen from the recurrence, however I have a recurrence of the form</p> <pre><code>T(n) = T((n/4)+3) + f(n) </code></pre> <p>How do I get the value of b in this case?</p> <p>This question <a href="https://cs.stackexchange.com/questions/11635/particularly-tricky-recurrence-relation-masters-theorem">Particularly Tricky Recurrence Relation (Master&#39;s Theorem)</a> is the only thing I found that has a similar case with T(n/4 +1) but gives no detail about how the b was calculated.</p> https://cs.stackexchange.com/questions/63981/-/63982#63982 2 Answer by iLoveCamelCase for Master Theorem: How to find the value of b in this recurrence relation iLoveCamelCase https://cs.stackexchange.com/users/17501 2016-09-28T01:28:43Z 2016-09-28T01:28:43Z <p>I don't think you can use master's theorem. However, there is a much more general version of that called <a href="https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method" rel="nofollow">Akra-Bazzi Method</a> which can be used to solve this problem</p> https://cs.stackexchange.com/questions/63981/-/64011#64011 2 Answer by D.W. for Master Theorem: How to find the value of b in this recurrence relation D.W. https://cs.stackexchange.com/users/755 2016-09-28T17:37:11Z 2016-09-29T17:52:18Z <p>You can't use the Master theorem on that function $T$.</p> <p>However, as Raphael suggests, you <em>could</em> consider the related function</p> <p>$$T'(n) = T'(n/4) + f(n),$$</p> <p>use the Master theorem to find a solution for $T'$, and then <em>check</em> whether that's a valid solution for $T$ too. No guarantees that it will be, but you could check.</p> <p>In other words, you could use the <em>guess-and-check</em> strategy to solve the recurrence for $T$, where your "guess" comes from solving $T'$ using the Master theorem. See also <a href="https://cs.stackexchange.com/q/2789/755">Solving or approximating recurrence relations for sequences of numbers</a> for an explanation of <em>guess-and-check</em> (also called <em>guess-and-prove</em>).</p> <p>One caveat is that guess-and-check will probably require an explicit solution to $T$, with specific constants. In other words, it's usually not enough to guess that $T(n) = O(g(n))$; you will typically need to guess a specific constant $c$ such that $T(n) \le c \cdot g(n)$, one that will enable the proof to go through.</p> https://cs.stackexchange.com/questions/63981/-/64040#64040 0 Answer by Euge for Master Theorem: How to find the value of b in this recurrence relation Euge https://cs.stackexchange.com/users/57425 2016-09-29T13:42:51Z 2016-09-29T13:42:51Z <p>What you can do is to use the master theorem to get lower and upper bounds separately, and then try to use other methods to prove a tight bound.</p> <p>So, on one hand we have</p> <p>$T(n) \leq T(n/3) + f(n)$ </p> <p>this is true because $T$ is an increasing function and $n/4 + 3 \leq n/3$ for $n$ big enough. </p> <p>You will be using the master theorem with the following recurrence: </p> <p>$T'(n) = T'(n/3) + f(n)$</p> <p>and getting $T'(n) \in \Theta(g(n))$ for some $g$. So you will conclude $T(n) \in O(g(n))$</p> <p>For the lower bound use $T(n) \geq T(n/4) + f(n)$.</p>