# Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi

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?

## 2 Answers

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)$$

• Yes but how would one go about doing it inductively? That is the key here. Feb 10, 2020 at 19:37
• @Iamlearningmath, knowing the right order you can try finding $c_1, c_2$ such that you can prove inductively that $c_1 n \le T(n) \le c_2 n$ (each one in turn; you might want to get tight values). Feb 12, 2020 at 0:22