1
$\begingroup$

I'm going through CLRS and was trying to solve for the asymptotic bound of the following recurrence (exercise 4-5.4) $$T(n) = 4T(n/2) + n^2\text{lg }n$$

According to CLRS definition of Master Theorem, I understood how case 2 doesn't apply here because $n^2\text{lg }n$ is not polynomially larger than $n^2$. According to wikipedia's definition of Master theorem, I understand that this would be case 2a; so the asymptotic notation of the recurrence would be $\Theta(n^2\text{lg}^{2}n)$. However, before going to Wikipedia, I tried to find an upper bound myself. Here's the work I did to try and show that $T(n)=O(n^2\text{lg }n)$ by induction.

$$ \begin{align*} T(n/2) &\leq c\left(\frac{n}{2}\right)^{2}\text{lg}\left(\frac{n}{2}\right) \hspace{6em}\text{Assume inductive step}\\ T(n) &\leq cn^2\text{lg}\left(\frac{n}{2}\right)+kn^2\text{lg }n \\ &\leq cn^2\text{lg}n-cn^2\text{lg }2+kn^2\text{lg }n \\ &\leq (c+k)n^2\text{lg }n\hspace{7em}\text{Drop negative term} \end{align*} $$

After solving problems, I usually check my answers here, as I think Rutgers does a great job showing work. However, all the answers I can find online (including Rutgers) for this exercise only seem to show the upper bound $O(n^2\text{lg}^{2}n$). Their work doesn't necessarily contradict the work that I showed, because they are proving an upper bound. However, Wikipedia contradicts my work because they give a tight bound with $\Theta$-notation.. I have asked my friends and online AI to check my work (the latter of which is just awful), and they can't seem to find any point they disagree on. Is my work misunderstanding the role of constants for the recurrence equation? I think it's trivial that $n^2\text{lg }n = o(n^2\text{lg}^{2}n)$... I just can't find where my work goes wrong

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ What is $k$? I assume it's a constant? If so, you cannot change the constant along the way, the same constant $c$ must apply to every $n$. That is, $c + k$ is larger than $c$, so $T(n)$ does not satisfies the inductive hypothesis. If we follow your argument for every $n$, the constant keeps increasing with $n$, so it's not a constant. $\endgroup$
    – Manuel Lafond
    Commented Jun 10 at 3:52
  • $\begingroup$ So essentially the inductive step must use the same constant as the assumption (which was c) and if it doesn't then the proof is invalid? $\endgroup$
    – Jackson Schuetzle
    Commented Jun 10 at 16:11
  • $\begingroup$ Yes exactly, $c$ could be any constant but it has to remain the same constant for every $n$. This is because the statement to prove is something like "There exists $c$ such that, for every $n$, $T(n) \leq c n^2 \lg n)$.". $\endgroup$
    – Manuel Lafond
    Commented Jun 11 at 20:33

1 Answer 1

Reset to default
1
$\begingroup$

The guess $T(n) \le cn^2\lg n$ does not work. Suppose it does, then we need to show the following:

\begin{aligned} 4c(n/2)^2\lg(n/2) + n^2\lg n & \le cn^2\lg n\\ \implies (c+1)n^2\lg n - cn^2 & \le cn^2\lg n\\ \implies n & \le 2^c\\ \end{aligned} This is a contradiction.

Whereas the guess $T(n) \le cn^2(\lg n)^2$ does work. I leave the verification upto reader (also given in the solution link mentioned above).

Improve this answer
$\endgroup$

Your Answer

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

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