0
$\begingroup$

I have tried solve the recurrence $T(n) = 5T(\frac{n}{2}) + n^2\lg^2 n$ using substitution. Apparently, it is exact for some $n$ and the order of the general solution can be found from this exact solution.

By substitution I got the following (not sure if it is correct):

$$T(n) = 5^kT(1) + \sum_{i = 0}^{k}{5^{i}\left(\frac{n}{2^{i}}\right)^{2}\lg^{2}\left(\frac{n}{2^{i}}\right)}$$

I am not sure how to proceed from this. I don't even know if this approach is correct so far. How do I solve this recurrence?

$\endgroup$
0
$\begingroup$

You can use the master theorem. This theorem allows you to solve some recurrences of the form $T(n) = aT(n/b) + f(n)$.

You need to compare $n^{\log_b a}$ with $f(n)$. In you case $n^{\log_b a} = n^{\log_2 5}$ and $f(n)=n^2 \log^2 n$.

There are different cases depending on how the above functions compare, but I am only going to discuss the one that is relevant to you (you can find more on Wikipedia).

In your case $f(n) = O(n^{\log_b a - c})$ for some constant $c>0$. To see this pick, e.g., $c=0.1$ and substitute to obtain: $n^2 \log^2 n = O(n^{\log_2 5 -0.1})$, which is true since $\log_2 5 - 0.1 > 2$.

The master theorem then tells you that $T(n) = \Theta(n^{\log_b a})$, which in your case is $T(n) = \Theta(n^{\log_2 5})$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But is this an exact solution? $\endgroup$ – bingbong Jun 11 at 21:21
  • $\begingroup$ What do you mean by "exact solution"? It is not an equality but since $T(n) \in \Theta(n^{\log_2 5})$ this tells you that there are two constants $c_1$ and $c_2$ with $0 \le c_1 \le c_2$ such that, for every sufficiently large value of $n$, $c_1 n^{\log_2 5} \le T(n) \le c_2 n^{\log_2 5}$. $\endgroup$ – Steven Jun 11 at 21:21
  • $\begingroup$ By exact solution I mean an equality. But I suppose, this is good enough. Thank you! $\endgroup$ – bingbong Jun 11 at 21:34
  • $\begingroup$ I am not familiar with the master theorem, could you show how to solve this problem with it in your solution? @Steven $\endgroup$ – bingbong Jun 11 at 21:34
  • $\begingroup$ I have edited my answer to add mode details. $\endgroup$ – Steven Jun 11 at 21:42

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.