How to prove $T(n) = T\left(\frac n4\right) + T\left(\frac{3n}4\right) + n$ is $\mathcal O(n\log n)$ using induction?

Question

How would you go about proving the recursion $$T(n) = T\left(\frac n4\right) + T\left(\frac{3n}4\right) + n$$is $\mathcal O(n\log n)$ using induction?

Thanks!

Answer 1

$$ T(n)=T(n/4)+T((3n)/4)+n $$

is a linear difference equation which can be solved as

$$ T(n) = T_h(n) + T_p(n)\\ T_h(n) = 0\\ T_p(n) = T_p(n/4)+T_p((3n)/4)+n $$

Now making

$$ T_h(n) = a^{\ln n} = e^{\lambda \ln n} = e^{\ln n^{\lambda}} = n^{\lambda} $$

we have

$$ n^{\lambda} = \left(\frac{n}{4}\right)^{\lambda}+\left(\frac{3n}{4}\right)^{\lambda} $$

or

$$ 4^{\lambda} = 1 + 3^{\lambda}\Rightarrow \lambda = 1 =\ln a \Rightarrow a = e \Rightarrow T_h(n) = n $$

etc.

Answer 2

I will assume that we are using the "floor" function, i.e. that $n/4$ and $3n/4$ denote the integral part of the quotient. With this convention, $T(19)=T(4)+T(12)+19$. Note that it is easy to tweak the proof to adapt to other cases.

Let $$M=\max \left\{\frac{T(2)}{2\log(2)},\frac{T(3)}{3\log(3)},\dots,\frac{T(7)}{7\log(7)},\frac{4}{\log(256/27)} \right\},$$ we will prove that $T(n) \leq M n \log n$ for all $n\geq 2$. (We must exclude $n=1$ since $T(1)$ can never be made smaller than a multiple of $1 \log 1 = 0$.)

The constant $M$ might look a bit scary, but it is simply crafted so that $T(n) \leq M n \log(n)$ for $2\leq n \leq 7$, and so that $M\geq \frac{4}{\log(256/27)}$, which we will see later is the crux of the proof.

Let us use strong induction to prove the result. The initialization step is trivial for $2\leq n \leq 7$, since we have constructed $M$ such that $T(n)\leq Mn\log n$ in these cases. For the induction step, let $n\geq 8$ be some integer, and let us assume that we have $T(k)\leq Mk\log k$ for all $2\leq k<n$.

We will first assume that $n$ is a multiple of $4$, since this is the easiest case. Denote $n=4m$, with our floor function convention we have $T(4m)=4m+T(m)+T(3m)$. Since $n\geq8$, $m\geq2$ and we can therefore use the induction hypothesis for $m$ and $3m$ to write: $$\begin{eqnarray}T(n) = T(4m) &\leq& 4m + Mm\log m + M.3m\log(3m) \\ &=& 4m + Mm\log (4m) - Mm\log4 + M.3m\log (4m) - M.3m\log(4/3) \\ &=& 4m + M.4m\log (4m) - Mm\log(4\times(4/3)^3) \\ &=& M.4m\log (4m) + m(\underbrace{4 - M\log(256/27)}_{\leq 0}) \\ &\leq& M.4m\log(4m) = Mn\log n \end{eqnarray}$$

Now, if $n$ is not a multiple of $4$, let us write $n=4m+k$ with $k \in \{1,2,3\}$. In this case we have $T(n)=T(m)+T(3m)+(4m+k)=T(4m)+k$, thus we can simply re-use what we just proved for $4m$: $$\begin{eqnarray}T(n) = T(4m+k) &=& T(4m)+k \\ &\leq& M.4m\log(4m) + k\times \underbrace{1}_{\leq M\log(4m)} \\ &\leq& M.4m\log(4m) + k.M\log(4m) = (4m+k)\log(4m) \\ &\leq& M(4m+k)\log(4m+k) = Mn\log n \end{eqnarray}$$