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

  • $\begingroup$ Yes but how would one go about doing it inductively? That is the key here. $\endgroup$ – Iamlearningmath Feb 10 at 19:37
  • $\begingroup$ @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). $\endgroup$ – vonbrand Feb 12 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.