<p>Not the standard statement of the generally used <a href="http://en.wikipedia.org/wiki/Master_theorem" rel="nofollow">Master theorem</a>, but the related <a href="http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method" rel="nofollow">Akra-Bazzi</a> theorem works.</p>

CC BY-SA 3.0
2014-10-14T10:01:41.940Z
2014-10-14T20:26:17.133Z
2014-10-14T20:26:17.133Z
daniello
<p>Is it possible to use the master theorem to find the asymptotic growth of a function of the form:
$$T(n) = aT(\frac{n}{b}+c)+f(n)$$
Where $c$ is a constant. Can we safely ignore this constant and use the master theorem?</p>

CC BY-SA 3.0
2014-10-14T22:12:22.933Z
Not quite ignore, but you can reduce it to the master theorem by a substitution $n\mapsto n+cb/(b-1)$.
Emil Jeřábek
CC BY-SA 3.0
2014-10-15T13:46:25.503Z
This question is not research-level and therefore off topic here.  I can either migrate it to CS.SE or close it.
Lev Reyzin
<time-complexity><asymptotics>
Using master theorem when there is a constant in the recursive term
msj
# Using master theorem when there is a constant in the recursive term

(Asked by: username_0 on 2014-10-14)

Is it possible to use the master theorem to find the asymptotic growth of a function of the form:
$$T(n) = aT(\frac{n}{b}+c)+f(n)$$
Where $c$ is a constant. Can we safely ignore this constant and use the master theorem?

**Tags:** time-complexity, asymptotics
> **Comments:**
> **username_1**: Not quite ignore, but you can reduce it to the master theorem by a substitution $n\mapsto n+cb/(b-1)$.  
> **username_2**: This question is not research-level and therefore off topic here.  I can either migrate it to CS.SE or close it.  

---

## 1 answers

### Answer by username_3 on 2014-10-14. Score: 6 | Accepted answer

Not the standard statement of the generally used [Master theorem](http://en.wikipedia.org/wiki/Master_theorem), but the related [Akra-Bazzi](http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method) theorem works.


---

