Proving time complexity of $T(n) = 2T(n/3 + 1) + n$
You can use the Akra–Bazzi theorem, a generalization of the master theorem.

Using the notations in the Wikipedia page:


$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 &lt; 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)$).