I have to prove that the recursion:
$$T(n) = T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + n
$$
is
$$
T(n) = Θ(n*\log n)$$
As you can see, the reccurence has two different terms that consist a T, namely $T(\frac{n}{3})$ and $T\left(\frac{2n}{3}\right)$. I can solve recurrences with one term but I'm not so sure how to apply the substitution method or the master method to recurrences with more than one recursive term. Or should I apply the tree method?
Best Answer
$% Predefined Typography \newcommand{\paren} [1]{\left({#1}\right)} \newcommand{\bparen}[1]{\bigg({#1}\bigg)} \newcommand{\brace} [1]{\left\{{#1}\right\}} \newcommand{\bbrace}[1]{\bigg\{{#1}\bigg\}} \newcommand{\floor} [1]{\left\lfloor{#1}\right\rfloor} \newcommand{\bfloor}[1]{\bigg\lfloor{#1}\bigg\rfloor} \newcommand{\mag} [1]{\left\lVert{#1}\right\rVert} \newcommand{\bmag} [1]{\bigg\Vert{#1}\bigg\Vert} \newcommand{\abs} [1]{\left\vert{#1}\right\vert} \newcommand{\babs} [1]{\bigg\vert{#1}\bigg\vert} % \newcommand{\labelt}[2]{\underbrace{#1}_{\text{#2}}} \newcommand{\label} [2]{\underbrace{#1}_{#2}} \newcommand{\ulabelt}[2]{\overbrace{#1}_{\text{#2}}} \newcommand{\ulabel} [2]{\overbrace{#1}_{#2}} % \newcommand{\setcomp}[2]{\left\{~{#1}~~\middle \vert~~ {#2}~\right\}} \newcommand{\bsetcomp}[2]{\bigg\{~{#1}~~\bigg \vert~~ {#2}~\bigg\}} % \newcommand{\iint}[2]{\int {#1}~{\rm d}{#2}} \newcommand{\dint}[4]{\int_{#3}^{#4}{#1}~{\rm d}{#2}} \newcommand{\pred}[2]{\frac{\rm d}{{\rm d}{#2}}#1} \newcommand{\ind} [2]{\frac{{\rm d} {#1}}{{\rm d}{#2}}} \newcommand{\predp}[2]{\frac{\partial}{\partial {#2}}#1} \newcommand{\indp} [2]{\frac{{\partial} {#1}}{\partial {#2}}} \newcommand{\predn}[3]{\frac{\rm d}^{#3}{{\rm d}{#2}^{#3}}#1} \newcommand{\indn} [3]{\frac{{\rm d}^{#3} {#1}}{{\rm d}{#2}^{#3}}} % \newcommand{\ii}{{\rm i}} \newcommand{\ee}{{\rm e}} \newcommand{\exp}[1] { {\rm e}^{\large{#1}} } % \newcommand{\and} {~\text{and}~} \newcommand{\xor} {~\text{xor}~} \newcommand{\or} {~\text{or}~} \newcommand{\T} {\text{True}} \newcommand{\F} {\text{False}} % \newcommand{\red} [1]{\color{red}{#1}} \newcommand{\blue} [1]{\color{blue}{#1}} \newcommand{\green}[1]{\color{green}{#1}} $
You can just use strong induction on the definition directly:
So inductively prove:
$$k_1 ~n~\log(n) \le T(n) \le k_2~ n~\log(n)$$ $$k_1 ~n~\log(n) \le T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + n \le k_2~ n~\log(n) \tag{A1}$$
So we are going to need the inductive assumptions that
$$k_1 ~\frac n3 ~\log \paren{\frac n3} \le T\paren{\frac{n}{3}} \le k_2~ \frac n3~\log \paren{\frac n3} \tag{A2}$$
$$k_1 ~\frac {2n}3 ~\log \paren{\frac {2n}3} \le T\paren{\frac{2n}{3}} \le k_2~ \frac {2n}3~\log \paren{\frac {2n}3} \tag{A3}$$
So applying (A2) and (A3) to (A1), it leaves 2 statements to prove, find $k_1$ and $k_2$ such that both of the following hold:
$$\begin{align} k_1 ~n~\log(n) ~\le~ & k_1 ~\frac n3 ~\log \paren{\frac n3} + k_1 ~\frac {2n}3 ~\log \paren{\frac {2n}3} + n \tag{B1} \\ & k_2~ \frac n3~\log \paren{\frac n3} + k_2~ \frac {2n}3~\log \paren{\frac {2n}3} + n ~\le~ k_2 ~ n~\log(n) \tag{C1} \end{align}$$
(B1) and (C1) may be simplified by combining the $n$ and $n~\log n$ expressions together:
$$0 ~\le~ \frac 13 \paren{k_1 \log\paren{\frac 13} + 2 k_1 \log\paren{\frac 23} + 3 } n \tag{B2}$$ $$0 ~\le~ -\frac 13 \paren{k_2 \log\paren{\frac 13} + 2 k_2 \log\paren{\frac 23} + 3} n \tag{C2}$$
So very small $k_1$ satisfy (B2) and very large $k_2$ satisfy (C2), so the induction is finished and the proposition is established.