Recurrence equation of $ T(n) = T(n/2 ) + dn\log_2(n)$

Question

I have the following equation:

$$T(n) = T\left({n \over 2}\right) + d n \log_2 n$$

A little investigation:

$T(2^1) = 1 + 2d$

$T(2^2) = T(2^1) + 2^2d\times 2 = 1 + 10d$

$T(2^3) = T(2^2) + 2^3d\times 3 = 1+34d$

I know the next one is by adding $2^nnd$ but I fail to see a pattern so I couldn't conclude $T(n)$ in a generic form.

Our teacher won't allow us to use the master theorem but instruct us to use a little investigation like what I did above, prove by induction afterwards.

Would someone help me? Thanks.

Answer 1

Proof by induction: Assume that, for some $n\geqslant1$ and some $c\gt0$, property $H_n(c)$ holds, where $$H_n(c):\qquad\forall k\leqslant n,\ T(k)\leqslant ck\log_2k.$$ Then $\log_2\left(\tfrac12(n+1)\right)\leqslant\log_2\left(n+1\right)$ and $n\log_2n\leqslant(n+1)\log_2(n+1)$ hence the upper bound $$T(n+1)= T(\tfrac12(n+1))+dn\log_2n\leqslant\tfrac12c(n+1)\log_2\left(\tfrac12(n+1)\right)+d(n+1)\log_2(n+1),$$ implies that $$T(n+1)\leqslant \left(\tfrac12c+d\right)(n+1)\log_2(n+1),$$ thus, $H_{n+1}(c)$ holds provided $$\tfrac12c+d\leqslant c.$$ Surely you can finish this.

Answer 2

We can solve another closely related recurrence that admits an exact solution and makes it possible to get precise bounds. Suppose we have $T(0)=0$ and $T(1)=1$ and for $n\ge 2$ $$T(n) = T(\lfloor n/2\rfloor) + q\times n\times\lfloor \log_2 n\rfloor.$$

Furthermore let the base two representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$

Then we can unroll the recurrence to obtain the following exact formula for $n\ge 2$ $$T(n) = 1 + q\sum_{j=0}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor - j) \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$ This follows more or less by inspection.

Now to get an upper bound consider a string of one digits, which gives $$T(n) \le 1 + q\sum_{j=0}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor - j) \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j} \\= 1 + q\left( 4 \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor} - 4 \times 2^{\lfloor \log_2 n \rfloor} - \frac{1}{2} (\lfloor \log_2 n \rfloor)^2 - \frac{1}{2} \lfloor \log_2 n \rfloor + 4\right).$$

For a lower bound consider a one followed by a string of zero digits, giving $$T(n) \ge 1 + q\sum_{j=0}^{\lfloor \log_2 n \rfloor} (\lfloor \log_2 n \rfloor - j) 2^{\lfloor \log_2 n \rfloor-j} \\ = 1 + q\left( 2 \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor} - 2 \times 2^{\lfloor \log_2 n \rfloor} + 2 \right).$$

Joining the dominant terms of the upper and the lower bound we obtain the asymptotics $$\color{#006}{q \lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor} \in \Theta\left(\log_2 n \times 2^{\log_2 n}\right) = \Theta\left(\log n \times n\right)}.$$

These are in agreement with what the Master theorem would produce.

Here is another computation in the same spirit: MSE link.