Bounds for $T(n) = 2T(n/2) + n/\lg{n}$

Question

I've been trying to find tight bounds for the equation:

$$ T(n) = 2T(n/2) + n/\lg{n} $$

The master method does not apply since $n/\lg{n}$ is not polynomially smaller than $n$. So far I've found that it is $\Omega(n)$ and $O(n\lg\lg{n})$. Both are easily verifiable with the substitution method. I've seen somewhere that it is $\Theta(n\lg\lg{n})$, but I cannot prove it. Can you help me?

Thanks!

Answer 1

Unrolling the recursion often helps see patterns.

$$\begin{align} T(n) &= 2 T\left(\frac{n}{2} \right) + \frac{n}{\lg n} = 4 T\left( \frac{n}{4} \right) + 2 \cdot \frac{n/2}{\lg(n/2)} + \frac{n}{\lg n} \\&= 4 T\left(\frac{n}{4} \right) + \frac{n}{(\lg n) - 1} + \frac{n}{\lg n} \end{align}$$

Suddenly, a pattern is evident! We can see how to unroll it an arbitrary number of steps. Going all the way, if $n = 2^m$:

$$ \begin{align}T(n) &= n T(1) + \sum_{i=0}^{m - 1} \frac{n}{(\lg n) - i} \\&= n T(1) + n \sum_{i=1}^{m} \frac{1}{m} \\&= \Theta(n \log m) = \Theta(n \lg \lg n) \end{align} $$

We could even do better:

$$ \begin{align} T(n) &= (1 + o(1)) n \log \lg n \\&= (1 + o(1)) n \log \log n \\&= \left(\log 2 + o(1) \right)) n \lg \lg n \end{align}$$

I'll leave it to you to deal with the details for when $n$ is not a power of $2$.

Answer 2

Here is a closely related recurrence that has an exact solution and is of the same complexity as the one in the original query. (This answers the comment from above concerning an exact solution for all $n$ and not just powers of two.)

Let $T(0) = 0$ and for $n\ge 1,$ $$ T(n) = 2 T(\lfloor n/2 \rfloor) + \frac{n}{1 + \lfloor \log_2 n \rfloor},$$ which also gives $T(1)=1$ BTW (a common base case).

By unrolling the recursion we see that for $n$ having binary digits $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k,$$ the exact answer for all $n\ge 1$ is given by $$T(n) = \sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k \frac{1}{1 + \lfloor \log_2 n \rfloor - k} \left(\sum_{j=k}^{\lfloor \log_2 n \rfloor} d_j 2^{j-k} \right).$$

For an upper bound consider the case of a string of one digits, giving (here the $H_q$ are the well known harmonic numbers) $$T(n) \le \sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k \frac{1}{1 + \lfloor \log_2 n \rfloor - k} \left(\sum_{j=k}^{\lfloor \log_2 n \rfloor} 2^{j-k} \right) = \sum_{k=0}^{\lfloor \log_2 n \rfloor} \frac{2^{\lfloor \log_2 n \rfloor +1}-2^k}{1 + \lfloor \log_2 n \rfloor - k} \\ = 2^{\lfloor \log_2 n \rfloor +1} H_{\lfloor \log_2 n \rfloor +1} -\sum_{k=1}^{\lfloor \log_2 n \rfloor +1} \frac{2^{\lfloor \log_2 n \rfloor +1 -k}}{k} = 2^{\lfloor \log_2 n \rfloor +1} H_{\lfloor \log_2 n \rfloor +1} -2^{\lfloor \log_2 n \rfloor +1 }\sum_{k=1}^{\lfloor \log_2 n \rfloor +1} \frac{2^{-k}}{k}.$$ This bound is exact and it is attained.

Now recall that $$\log\frac{1}{1-z} = \sum_{k\ge 1}\frac{z^k}{k} \quad\text{so that}\quad \sum_{k\ge 1}\frac{2^{-k}}{k} = \log\frac{1}{1-1/2} = \log 2.$$ It follows that the upper bound is asymptotic to $$2^{\lfloor \log_2 n \rfloor +1} (H_{\lfloor \log_2 n \rfloor +1}-\log 2).$$

The lower bound is even simpler and represents the case of a one followed by a string of zeros, giving $$T(n) \ge \sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k \frac{1}{1 + \lfloor \log_2 n \rfloor - k} 2^{\lfloor \log_2 n \rfloor -k} = 2^{\lfloor \log_2 n \rfloor} \sum_{k=0}^{\lfloor \log_2 n \rfloor} \frac{1}{1 + \lfloor \log_2 n \rfloor - k} \\ = 2^{\lfloor \log_2 n \rfloor} H_{\lfloor \log_2 n \rfloor +1}.$$ This bound is once more an exact one and it is actually attained and hence cannot be improved upon.

Finally taking the upper and the lower bound together we see that $$T(n) = \Theta\left(2^{\lfloor \log_2 n \rfloor} H_{\lfloor \log_2 n \rfloor +1}\right) = \Theta\left(2^{\log_2 n} \log (\lfloor \log_2 n \rfloor +1)\right).$$ Continuing the simplification we get $$ \Theta\left(n \log (\lfloor \log_2 n \rfloor +1)\right) = \Theta\left(n \log \log n\right)$$ as claimed.

This link points to a series of similar calculations.