3

I'm trying to solve the following recurrence relation

$$T(n)\le T\left(\frac{3n}{4}\right)+T\left(\frac{n}{\log n}\right)+C\cdot{n}\log\log n$$

The answer should be $T(n)=\Theta(n \log\log n)$ and I can show it by induction, but how should one guess that this is the form of answer?

Galc127
  • 4,451
  • I would first look to the master theorem; to simplify the two $T$'s on the RHS, I would focus on the one that has the largest growth (for $n$ sufficiently large, $\frac{3n}{4}>\frac{n}{\log n}$). So then, for $n$ sufficiently large, $T(n)\leq 2T(\frac{3n}{4})+C\cdot n\log\log n$. I haven't done out the details to see if this actually works, however. – Michael Burr Mar 22 '16 at 18:35
  • @MichaelBurr, Following your suggestion, we have $f(n)=n\log\log n=O(n^2)$ and $2<\log_{\frac{4}{3}}2$, thus we have case 1 of master theorem, i.e $T(n)=\Theta \left(n^{\log_{\frac{4}{3}}2}\right)$ which is not strict... – Galc127 Mar 22 '16 at 18:58
  • 1
    You could, instead, choose $n$ even larger so that one of the other cases of the master theorem apply. For example, $T(\frac{n}{\log n})<\frac{1}{3} T(\frac{3n}{4})$ – Michael Burr Mar 22 '16 at 19:02
  • @MichaelBurr, this one is great, thanks! – Galc127 Mar 22 '16 at 19:05
  • To get Case 3 to apply, don't you need then something strictly less that $1/3$? (to get "$a< 4/3$")? @MichaelBurr – Clement C. Mar 22 '16 at 19:10
  • @Clement C., this is true, we need little less than 1/3 in order to apply it. The inequality is indeed strict. – Galc127 Mar 22 '16 at 19:15
  • I agree that the constant needs to be a little smaller; thanks for noticing @ClementC. – Michael Burr Mar 22 '16 at 19:17

0 Answers0