1
$\begingroup$

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it because of master theorem), and to find an upper bound, I use induction. I tried to show that $T(n)\leq cn^{2}\log n$ but that did not work, I got $T(n)\leq cn^{2}\log n+n^{2}$. Then I tried to show that, if $T(n)\leq c_{1}n^{2}\log n-c_{2}n^{2}$, then it is also $O(n^{2}\log n)$, but that also did not work and I got $T(n)\leq c_{1}n^{2}\log(n/2)-c_{2}n^{2}+n^{2}$. What trick can I do to show that? Thanks

$\endgroup$
  • $\begingroup$ What happens when $n$ is odd or just not a power of $2$? $\endgroup$ – Dennis Gulko Mar 3 '13 at 12:37
  • $\begingroup$ We can ignore these cases $\endgroup$ – Yasin Razlık Mar 3 '13 at 12:39
  • $\begingroup$ In that case perhaps it would be better to write $t(2n)=4t(n)+n^{2}$? $\endgroup$ – preferred_anon Mar 3 '13 at 12:42
  • $\begingroup$ Its probably $T(\lfloor \frac{n}{2} \rfloor)$, but the floor doesn't make a difference when analysing asymptotic behaviour. $\endgroup$ – Ivan Loh Mar 3 '13 at 12:48
4
$\begingroup$

If $T(\frac{n}{2}) \leq c(\frac{n}{2})^2\log_2(\frac{n}{2})+T(1)$, then \begin{align} T(n)=4T\left(\frac{n}{2}\right)+n^2 & \leq 4c\left(\frac{n}{2}\right)^2\log_2\left(\frac{n}{2}\right)+4T(1)+n^2 \\ &=cn^2\log_2(n)-cn^2+4T(1)+n^2 \\ &\leq cn^2\log_2(n)+T(1) \end{align} for $c \geq 1+3T(1)$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks, but i did not understand how you get -cn^2 at the 3rd line? $\endgroup$ – Yasin Razlık Mar 3 '13 at 13:01
  • $\begingroup$ i get it now, thank you! $\endgroup$ – Yasin Razlık Mar 3 '13 at 13:05
1
$\begingroup$

By way of enrichment we solve another closely related recurrence that admits an exact solution. Suppose we have $T(0)=0$ and for $n\ge 1$ (this gives $T(1)=1$) $$T(n) = 4 T(\lfloor n/2 \rfloor) + n^2.$$

Furthermore let the base two representation of $n$ be $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$

Then we can unroll the recurrence to obtain the following exact formula for $n\ge 1$ $$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 4^j \left( \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j} \right)^2 = \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k\right)^2.$$

Now to get an upper bound consider a string of one digits which yields $$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} \left(\sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k\right)^2.$$

Note that this bound is attained and cannot be improved. It simplifies to $$\left(4 \lfloor \log_2 n \rfloor - \frac{8}{3}\right) \times 4^{\lfloor \log_2 n \rfloor} + 4 \times 2^{\lfloor \log_2 n \rfloor} - \frac{1}{3}.$$

The lower bound is for the case of a one digit followed by a string of zeros and yields $$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^{2\lfloor \log_2 n \rfloor}.$$ It simplifies to $$(1+\lfloor \log_2 n \rfloor) 2^{2\lfloor \log_2 n \rfloor}.$$

Joining the dominant terms of the upper and the lower bound we obtain the asymptotics $$\color{#006}{\lfloor \log_2 n \rfloor 2^{2 \lfloor \log_2 n \rfloor} \in \Theta\left(\log_2 n \times 2^{2 \log_2 n}\right) = \Theta\left(\log n \times n^2\right)}.$$

These are both in agreement with what the Master theorem would produce.

This MSE link has a series of similar calculations.

| cite | improve this answer | |
$\endgroup$

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.