Solving the recurence $T(n) = T(n/5) + T(7n/10) + n$ using substitution method

Question

I am not sure how to handle this problem given no base case. Is it enough to assume that $T(n/5) + T(7n/10) <= c(n/5) + c(7n/10)$, and substitute that back in? This seems like a weak way of proving it.

Answer 1

Your assumption is right. We claim that that $T\left(n\right)=\mathcal{O}\left(n\right)$. Then, we must show that there exists $c_{1}>0$ and $n_{0}$ such that for all $n\ge n_{0}$, $T\left(n\right)\le c_{1}n$. For the base case, since you are given no information on this, the only reasonable thing that I see is that you would substitute $n=0$ and be forced with $T\left(0\right)=0$, which satisfies $T\left(0\right)=0\le c_{1}\cdot0$. Now assume that for all $k<n$, $T\left(k\right)\le c_{1}k$. Then,

\begin{align*} T\left(n\right)&=T\left(\frac{n}{5}\right)+T\left(\frac{7n}{10}\right)+n\\ &\le c_{1}\frac{n}{5}+c_{1}\frac{7n}{10}+n\\ &=\left(\frac{9c_{1}+10}{10}\right)n. \end{align*}

We want to find $c_{1}>0$ such that $\left(\frac{9c_{1}+10}{10}\right)n\le c_{1}n$ for all $n\ge n_{0}$. Rearranging this inequality, we end up with $10n\le c_{1}n$ and so $c_{1}\ge10$ when $n\ge0$. Thus, we have shown by the substitution method that $T\left(n\right)=\mathcal{O}\left(n\right)$.

By a similar argument (except replacing $T\left(k\right)\le c_{1}k$ with $T\left(k\right)\ge c_{2}k$), we see that $0<c_{2}\le10$ for all $n\ge0$ and end up with that $T\left(n\right)=\Omega\left(n\right)$. Thus, $10n\le T\left(n\right)\le 10n$, giving us that $T\left(n\right)=10n$ for all $n\ge0$ and so $T\left(n\right)=\Theta\left(n\right)$.

There is an alternative way to go about this as well. If we suppose that $T\left(x\right)=\Theta\left(x\right)$ (I have changed the domain from $\mathbb{N}$ to $\mathbb{R}$) from the start, then we know that $T\left(x\right)=ax+b$ for some $a,b\in\mathbb{R}$. Substituting this into our recurrence relation, we have \begin{align*} ax+b&=\frac{1}{5}\left(ax+b\right)+\frac{7}{10}\left(ax+b\right)+x\\ &=\frac{9a+10}{10}x+\frac{9}{10}b. \end{align*}

Comparing coefficients on the left and right sides of the equation, we arrive at $a=10$ and $b=0$, giving us $T\left(x\right)=10x$.