Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

2 Answers 2

up vote 2 down vote accepted

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)$.

share|improve this answer
    
Thanks, but i did not understand how you get -cn^2 at the 3rd line? –  bigO Mar 3 '13 at 13:01
    
i get it now, thank you! –  bigO Mar 3 '13 at 13:05

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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