4
$\begingroup$

I am interesting in the asymptotic rate of growth of the following recursion:

$$ T(n) = 2T(n/2) + \frac{T(n − 1)}{\log n}, $$ with base case $T(1) = 1$.

I'm having trouble of solving this recurrence problem, it seems much more tricky than I initially thought, and I'm totally stuck after doing some unrolling. What is a good way to approach this question?

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you have a guess on the solution of the recurrence? $\endgroup$
    – Steven
    Nov 4, 2019 at 19:28
  • $\begingroup$ I'm guessing nlogn but not sure how to verify it. $\endgroup$
    – ran wty
    Nov 4, 2019 at 19:39

1 Answer 1

Reset to default
3
$\begingroup$

By comparison to the recurrence $T(n) = 2T(n/2)$, we see that $T(n) = \Omega(n)$. By comparison to the recurrence $T(n) = 2T(n/2) + n$, we see that actually $T(n) = \Omega(n\log n)$.

Now let us prove by induction that the other direction holds as well. I will interpret $T(n/2)$ as $T(\lfloor n/2 \rfloor)$. Suppose that $T(m) \leq Cm\log m$ for all $m < n$. Then $$ T(n) \leq 2C\frac{n}{2}\log \frac{n}{2} + \frac{n\log n}{\log n} = Cn\log n + (1-C)n. $$ For $C \geq 1$, it follows that $T(n) \leq Cn\log n$.

It seems that we have proved that $T(n) = O(n\log n)$, but actually the base case of the induction doesn't hold. However, this shouldn't be too hard to fix (left to the reader).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks, I figured it out. $\endgroup$
    – ran wty
    Nov 5, 2019 at 1:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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