# Prove recurrence T(n) = 2T(n/2) + n/lgn is O(nlglgn) using Substitution Method

Prove that $$T(n) = 2T(\frac{n}{2}) + \frac{n}{\log_2n}$$ is $$O(n\log_2\log_2n)$$, where $$T(1) = Θ(1)$$.

I tried to form the Induction Hypothesis but didn't succeed in choosing the right one.

Try 1:

If we assume $$0 ≤ ck\log_2\log_2k,\forall k < n$$, must show $$T(n) ≤ cn\log_2\log_2n$$.

$$T(\frac{n}{2}) ≤ c(\frac{n}{2})\log_2(\log_2n - 1),\because \frac{n}{2} = k < n$$ \begin{align} & T(n) ≤ cn\log_2(\log_2n - 1) + \frac{n}{\log_2n}\\ & ≤ cn\log_2\log_2n + \frac{n}{\log_2n}\\ \end{align} but this expression is never less than $$cn\log_2\log_2n$$, due to the positive $$\frac{n}{\log_2n}$$ term.

Try 2:

Assume $$0 ≤ ck\log_2\log_2k - \frac{bk}{\log_2k}, \forall k < n$$, must show $$T(n) ≤ cn\log_2\log_2n - \frac{bn}{\log_2n}$$.

$$T(\frac{n}{2}) ≤ c(\frac{n}{2})\log_2(\log_2n - 1) - \frac{bn}{2(\log_2n - 1)}, \because \frac{n}{2} = k < n$$ \begin{align} & T(n) ≤ cn\log_2(\log_2n - 1) - \frac{bn}{(\log_2n - 1)} + \frac{n}{\log_2n}\\ & ≤ cn\log_2\log_2n - \frac{bn}{\log_2n} + \frac{n}{\log_2n}\\ \end{align} If we factor the $$\frac{-n}{\log_2n}$$ out, we get $$cn\log_2\log_2n - \frac{n}{\log_2n}(b - 1)$$. Once again, it's never less than $$cn\log_2\log_2n - \frac{bn}{\log_2n}$$ because its $$\frac{n}{\log_2n}$$ negative factor is bigger.

I tried reforming the inductive hypothesis to be $$ck\log_2\log_2k - \frac{2bk}{\log_2k}$$, $$ck\log_2\log_2k - \frac{bk}{2\log_2k}$$, $$ck\log_2\log_2k + \frac{bk}{\log_2k}$$, but I can never get my expression bounded.

Any suggestions?

Let $$S(n) = T(n)/n$$, so that $$S(n) = \frac{T(n)}{n} = \frac{2T(n/2)}{n} + \frac{1}{\log_2 n} = S(n/2) + \frac{1}{\log_2 n}.$$ Suppose now that $$n = 2^k$$, and suppose $$S(1) = T(1) = C$$. Then $$S(2^k) = S(2^{k-1}) + \frac{1}{k},$$ and so unrolling, we get $$S(2^k) = \frac{1}{k} + \cdots + \frac{1}{\ell} + S(2^{\ell-1}).$$ In particular, taking $$\ell = 1$$, this gives $$S(2^k) = \frac{1}{k} + \cdots + \frac{1}{1} + S(1) = H_k + C,$$ where $$H_k$$ is the harmonic number, well-known to satisfy $$H_k = \ln k + O(1)$$. Therefore if $$n = 2^k$$ then $$T(n) = nS(n) = n\ln\log_2 n + O(n).$$ Using more accurate asymptotics of the harmonic number, we can find an even better approximation to $$T(n)$$, for example $$T(n) = n\ln\log_2 n + (\gamma+C) n + \frac{1}{2} + O\left(\frac{1}{n}\right).$$
• sorry for not being able to handle this given your hint. as I understood if I prove that $S(n)$ is $O(\log_2\log_2n)$, then $T(n)$ is $O(n\log_2\log_2n)$. but while trying to prove $S(n)$, I face the same problem of not being able to get rid of the fraction positive term. So far I've only seen the non-recurrent part as some standard functions, I searched the internet and never found one with a fraction instead. Also, if only $T(n/2)$'s factor was bigger than 2, I could've worked more with terms. Can you maybe give me links to similar problems or give another tiny hint? Feb 16, 2022 at 13:06
• assuming $S(n) ≤ c\log_2\log_2k$, $S(n) = c\log_2(\log_2n - 1) + \frac{1}{\log_2n} = c\log_2(\log_2n(1 - \frac{1}{\log_2n})) + \frac{1}{\log_2n} = c\log_2\log_2n + c\log_2(1 - \frac{1}{\log_2n})+ \frac{1}{\log_2n} ≤ c\log_2\log_2n + \frac{1}{\log_2n} - \frac{c}{\log_2n} ≤ c\log_2\log_2n$, as long as $c > 0$. Take $c = 1$, then $S(n) = O(\log_2\log_2n)$ Feb 17, 2022 at 14:05