patternMinor
Solving $T(n) = 2T(n/2) + T(n-1)/\log n$
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?
$$ 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).
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.