0
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Yes but how would one go about doing it inductively? That is the key here. $\endgroup$ Feb 10, 2020 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, 2020 at 0:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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