Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
We know that the complexity of $T(n)=2T(n/3 + 1) + n$ is $\Theta(n)$, as has been proved on this exchange before. However, what about proving it inductively? I believe that this method might work.
Guess $T(n) \leq cn-d$. Assume true for $m < n$. Specifically, $m = n/3 < n$ Then, $T(n) \leq cn-d$.
$T(n) \leq 2(cn/3 - d + 1) + n$ $= 2cn/3 - 2d + 2 + n$ $=n(2c/3+1)+2(1-d)$. Then for values of $c \geq 1$ and $d \geq2$ we have $T(n) \leq cn - d$. Then $T(n)=\Theta(n)$.
What does everyone think?
You want to prove a tight $\Theta(n)$ bound as @vonbrand commented you could to show: $$am+b \leq T(m)\leq cm+d\quad (1)$$ Now start by assuming $(1)$ holds for all $m < n$ and conclude: $$T(n) = 2T(n/3+1)+n \geq 2(a(n/3+1)+b)+n \geq n(2/3a+1) + 2(a+b)$$ $$T(n) = 2T(n/3+1)+n \leq 2(c(n/3+1)+d)+n \leq n(2/3c+1) + 2(c+d)$$ Thus $an+b \leq T(n)\leq cn+d$. Hence $T(n) \in \Theta(n).$
You can use the variant by Leighton "Notes on Better Master Theorems for Divide-and-Conquer Recurrences". Lehman, Leighton and Meyer in "Mathematics for Computer Science" on page 1019 state a simplified version: If you have $T(n) = \sum_{1 \le i \le k} a_i T(b_i n + h_i(n)) + g(n)$, where $a_i > 0$, $0 < b_i < 1$, $g(n) > 0$ such that $\lvert g'(x) \rvert$ is bounded by a polynomial, and $\lvert h_i(n) \rvert = O(n / \log^2 n)$, then is $p$ is the unique real such that $\sum_{1 \le i \le k} a_i b_i^p = 1$, then:
$$ T(n) = \Theta\left( n^p \left( 1 + \int_1^n \frac{g(u)}{u^{p + 1}} d u \right) \right) $$
Your $g(n) = n$ certainly qualifies. With $a_1 = 2$, $b_1 = 1/3$, $h_1(n) = 1$ satisfies the condition, you get:
$$ 2 \cdot 3^{-p} = 1 $$
from which $p = \log_3 2$, so that:
$$ T(n) = \Theta\left( n^{\log_3 2} \left( 1 + \int_1^n u^{- \log_3 2} d u \right) \right) = \Theta(n) $$
