$T(n)=T(\frac{n}{3})+T(\frac{2n}{3})+cn$

Question

I'm trying to understand the following proof from 'Introduction to Algorithms' that the recurrence $T(n)=T(n/3)+T(2n/3)+cn$ has solution $O(n lg n)$.

I'm stuck on the fourth step when he replaces $-d(2n/3)lg(3/2)$ with just $(2n/3)lg(3/2)$ i.e. he replaces $-d$ with $1$.

Should this be an inequality rather than an equality. It would make sense if it was less than or equal to.

$d \ge c/(lg(3)-2/3)$

Answer 1

Adding color, and changing some of the brackets from round to square, the fourth step is $$ \begin{aligned} &\left[ \color{red}{d(n/3)\lg n} - d(n/3)\lg 3\right] + \left[\color{red}{d(2n/3)\lg n}-d(2n/3)\lg(3/2)\right] + cn\\ &=\color{red}{dn\lg n}-d\left[(n/3)\lg 3+(2n/3)\lg(3/2)\right]+cn \end{aligned} $$ Looks like they factored out $-d$; it wasn't replaced by $1$.

Answer 2

They just factored out $-d$, and the coefficient is not replaced by $1$. Thus the sign $=$ is correct.