2
$\begingroup$

The guess solution to the

$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

is $\Theta(n \log{\log n})$. This is my solution: $$ T(n) \leq 2c\left(\frac{n}{2}\right) \log{\log {\frac{n}{2}}} + \frac{n}{\log n} \\ \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\ \leq cn \log{\log {n}} + \frac{n}{\log n} $$

that fails to for the $T(n) \leq cn \log{\log {n}}$

Now I try to solve the $T(n) \leq c(\log \log n - \frac{n}{\log n})$, we have $$ T(n) \leq 2c\left(\left(\frac{n}{2}\right) \log \log {\frac{n}{2}} - \frac{\frac{n}{2}}{\log {\frac{n}{2}}}\right) + \frac{n}{\log n}\\ \leq cn \log \log {\frac{n}{2}} - \dfrac{n}{\log n - 1} + \dfrac{n}{\log n}\\ \leq cn \log \log {n} - \dfrac{n}{\log n - 1} + \dfrac{n}{\log n}\\ $$ and it will never be $\leq cn \log \log {n} - \dfrac{n}{\log n}$

How can I solve the recurrence?

$\endgroup$
2
  • $\begingroup$ $\log(x)$ is a function taking an input, I'm not familiar with the notation $\log^n$. Do you perhaps mean $\log n$ or $\log(n)$? $\endgroup$ – ryan May 12 '17 at 3:24
  • $\begingroup$ @ryan you are right $\endgroup$ – M a m a D May 12 '17 at 3:34
7
$\begingroup$

$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

Would yield the following summation (assuming $n$ is a power of 2 and base case is $n=2$):

$$ \begin{align} T(n) &= \frac{n}{\log n} + 2 \frac{\frac{n}{2}}{\log \frac{n}{2}} + 4 \frac{\frac{n}{4}}{\log \frac{n}{4}} + \dots \\ & = \frac{n}{\log n} + \frac{n}{\log \frac{n}{2}} + \frac{n}{\log \frac{n}{4}} + \dots + n\\ & = n \left[\frac{1}{\log n} + \frac{1}{\log(n) - 1} + \frac{1}{\log(n) - 2 } + \dots + 1\right]\\ & = n \sum_{i = 0}^{\log n - 1} \frac{1}{\log(n) - i}\\ & = n \cdot H_{\log n}\\ \end{align} $$

Where $H_n$ is the $n$th Harmonic number. It's known that $H_n = \Theta(\log n)$.

We can thus conclude $$T(n) = \Theta( n \log \log n )$$

Now with this being said; I believe this issue in your logic is the following steps: $$ \begin{align} T(n) & \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\ & \leq cn \log{\log {n}} + \frac{n}{\log n} \end{align} $$ The jump from step 1 to step 2, while not incorrect, is not tight. Which is why you're not meeting the necessary conclusion. It should be something like: $$ \begin{align} T(n) & \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\ & \leq cn \left[\log \log \frac{n}{2} + \frac{1}{\log n}\right] \end{align} $$ It can then be proven by induction that:

$$\log_2 \log_2 \frac{n}{2} + \frac{1}{\log_2 n} < \log_2 \log_2 n$$

For $n > 2$. The proof is pretty straightforward and I'll leave it as an exercise for the reader, but it then follows that:

$$ T(n) \leq cn \log\log n $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.