Htykuut

I have to prove that the recursion:

$$T(n) = Tleft(frac{n}{3}right) + Tleft(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 $Tleft(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?

$% 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]{leftlfloor{#1}rightrfloor}
newcommand{bfloor}[1]{bigglfloor{#1}biggrfloor}
newcommand{mag} [1]{leftlVert{#1}rightrVert}
newcommand{bmag} [1]{biggVert{#1}biggVert}
newcommand{abs} [1]{leftvert{#1}rightvert}
newcommand{babs} [1]{biggvert{#1}biggvert}
%
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}}
$

$$T(n) = T paren{ frac{n}{3} } + Tparen{ frac{2n}{3} } + n$$
$$Downarrow$$
$$T(n) = Theta(n~log n)$$

You can just use strong induction on the definition directly:

For some positive $k_1$ and $k_2$, and $n_0$:
$$f in Theta(g)$$
is defined as
$$forall n > n_0 quad k_1~g(n) le f(n) le k_2 ~ g(n)$$

So inductively prove:

$$k_1 ~n~log(n) le T(n) le k_2~ n~log(n)$$
$$k_1 ~n~log(n) le Tleft(frac{n}{3}right) + Tleft(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
Tparen{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
Tparen{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 logparen{frac 13} + 2 k_1 logparen{frac 23} + 3 } n tag{B2}$$
$$0 ~le~ -frac 13 paren{k_2 logparen{frac 13} + 2 k_2 logparen{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.