HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Solving $T(n) = 2T(n/2) + T(n-1)/\log n$

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
solvinglogstackoverflow

Problem

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?

Solution

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).

Context

StackExchange Computer Science Q#116675, answer score: 3

Revisions (0)

No revisions yet.