Exercise 4.3-5

[aschroede]

If the recurrence relation is $$ T(n) = T(\lceil n / 2 \rceil) + T(\lfloor n / 2 \rfloor) + \Theta(n) $$

And our inductive hypothesis for the upper bound is $$ T(n) \le c(n-2)\lg(n-2) -2c $$

Then the first line of the solution should be $$ T(n) \le c(\lceil n / 2 \rceil -2 )\lg(\lceil n / 2 \rceil - 2) \textbf{ -2c } + c(\lfloor n / 2 \rfloor - 2)\lg(\lfloor n / 2 \rfloor - 2) \textbf{ -2c } + dn $$

Instead of $$ T(n) \le c(\lceil n / 2 \rceil -2 )\lg(\lceil n / 2 \rceil - 2) + c(\lfloor n / 2 \rfloor - 2)\lg(\lfloor n / 2 \rfloor - 2) + dn $$

Note that the second line of the solution is correct as it has the two $ -2c $ terms, it is only the first line that is incorrect.

[aschroede]

Also how is it true that the third and fourth lines of the solution are equal?

$$ c(n / 2 - 1 )\lg(n / 2 - 1) + c(n / 2 - 1)\lg(n / 2 - 1) + dn = c\frac{n - 2}{2}\lg\frac{n - 2}{2} + c\frac{n - 2}{2}\lg\frac{n - 2}{2} \textbf{ - 4c } + dn $$

Where does the $ -4c $ term come from in the fourth line of the solution (second line here)?

Additionally, it is stated that the last step in the solution hold for $ c > d $, I believe this should be $ c \ge d $

[aschroede]

Between the issues previously mentioned I think the solution would be better written as the following.

For $ O(n\lg n) $, we guess $T(n) \le c(n-2)\lg(n-2) - 2c $,

$$ \begin{aligned} T(n) & \le c(\lceil n / 2 \rceil -2 )\lg(\lceil n / 2 \rceil - 2) -2c + c(\lfloor n / 2 \rfloor - 2)\lg(\lfloor n / 2 \rfloor - 2) -2c + dn \\ & \le c(n/2 + 1 - 2) \lg(n/2 + 1 - 2) + c(n/2 + 1 - 2)\lg(n/2 + 1 - 2) - 4c + dn \\ &= 2c(n/2 - 1) \lg(n/2 - 1) - 4c + dn \\ & = c(n - 2) \lg(\frac{n-2}{2}) - 4c + dn \\ & = c(n - 2) \lg(n-2) - c(n-2)\lg(2) - 4c + dn \\ & = c(n - 2) \lg(n-2) - c(n-2) - 4c + dn \\ & = c(n - 2) \lg(n-2) -2c + (d-c)n \\ & \le c(n - 2) \lg(n-2) -2c \end{aligned}$$

Where the last step holds for $ c \ge d $.

We can go from line 1 to line 2 because $ (n/2+1) \ge \lceil n/2 \rceil, \lfloor n/2 \rfloor $