# Proving time complexity of $T(n) = 2T(n/3 + 1) + n$

I am working on proving the time complexity for the following problem, but believe I am stuck:

$$T(n) = 2T(n/3 + 1) + n$$

However, I still cannot seem to find the answer. Using this proof from a Dartmouth course:

$$a = 2, b = 3, c = 1$$

In this case, I know logb a is .63, which is less than 1, so the complexity is $$Θ(n)$$. However, I don't know how to prove that.

I am trying to practice with the methods that I "know" - Master Theorem, Substitution, Iteration, or a Recursion Tree. And using one of those 4 methods, I can't find a way to prove the complexity is $$Θ(n)$$, even though I know that's the answer.

Would anyone be able to assist?

• You can use the Akra–Bazzi theorem, a generalization of the master theorem. – Yuval Filmus Sep 20 '18 at 3:43
• Hi @YuvalFilmus , thank you for the suggestion. I read through the page that you hyperlinked but can't see how this algorithm is solvable by Akra-Bazzi. – wundermahn Sep 20 '18 at 15:28
• Recurrence relations don't have time complexities! Recurrences are simply sets of equations which have a solution, and that solution is a function. Suppose instead that you're told that apples cost $a$ and pears cost $p$. Asking for the time complexity of a recurrence is like asking for the cost of the equations $4a+2p=8$, $3a+3p=9$. The solutions to those equations tell you the cost of the things, but it makes no sense to ask about the "cost" of the equations. – David Richerby Sep 21 '18 at 11:20
• Also, you're not trying to "solve an algorithm by Akra-Bazzi". The thing you're trying to solve is a recurrence relation; an algorithm is a sequence of instructions for performing some task. – David Richerby Sep 21 '18 at 11:22

You can use the Akra–Bazzi theorem, a generalization of the master theorem.

• $g(x) = x$
• $k = 1$
• $a_i = 2$
• $b_i = 1/3$
• $h_1(x) = 1$ (in fact, probably $h_1(x)$ is a bit different, since $n/3+1$ isn't always an integer)
• $x_0$ is a constant which is missing from your recurrence relation
You can easily check that all conditions of the theorem hold. To get the asymptotics, we first compute the value of $p$, which is the solution to $2(1/3)^p = 1$, that is, $p = \log_3 2$. Next, we calculate the integral appearing in the answer formula: $$\int_1^x \frac{u}{u^{p+1}} \, du = \int_1^x u^{-p} \, du = \frac{x^{1-p}-1}{1-p}.$$ We conclude that $$T(x) = \Theta\left(x^p\left(1 + \frac{x^{1-p}-1}{1-p}\right)\right) = \Theta(x^p + x) = \Theta(x^{\max(p,1)}).$$ Since $p < 1$, the answer is $T(x) = \Theta(x)$.
More generally, the Akra–Bazzi theorem shows that the master theorem applies even when the applications of $T$ on the right-hand side of the recurrence are off by a small amount (at most $O(x/\log^2 x)$).