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?

$\endgroup$
2
  • $\begingroup$ Do you have a guess on the solution of the recurrence? $\endgroup$ – Steven Nov 4 '19 at 19:28
  • $\begingroup$ I'm guessing nlogn but not sure how to verify it. $\endgroup$ – ran wty Nov 4 '19 at 19:39
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).

$\endgroup$
1
  • $\begingroup$ Thanks, I figured it out. $\endgroup$ – ran wty Nov 5 '19 at 1:40

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.