If I were to solve the recurrence of following equation and give asymptotic upper and lower bounds:
$$T(n) = 4T(\frac{n}{2}) + n^2 + n$$
Can I apply Master Theorem on this?
My attempt was following:
Then,
$f(n) = n^2 + n$
$c = 2$ so it has $O(n^2)$
$a = 4, b = 2,$
$n^{\log_b a} = n^{\log_2 4} = n^2$
Therefore, I applied Case 2, since $n^2+n = \Theta (n^2)$
Can you correct me on this?
Best Answer
Suppose we are trying to solve the recurrence $$T(n) = 4 T(\lfloor n/2 \rfloor) + n^2+n$$ where $T(0)=0.$
Let the binary digits of $n$ be given by $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$
Now unroll the recurrence to get the following exact formula: $$T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 4^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} \left(d_k 2^{k-j}\right)^2 + \sum_{j=0}^{\lfloor \log_2 n \rfloor} 4^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$
To get an upper bound consider the string of one digits, which gives $$T(n) \le \sum_{j=0}^{\lfloor \log_2 n \rfloor} 4^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} \left(2^{k-j}\right)^2 + \sum_{j=0}^{\lfloor \log_2 n \rfloor} 4^j \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j}.$$ This simplifies to $$\lfloor \log_2 n \rfloor \times 4^{\lfloor \log_2 n \rfloor +1} + 2^{\lfloor \log_2 n \rfloor +1}.$$
For a lower bound consider a one digit followed by zeros, which gives $$T(n) \ge \sum_{j=0}^{\lfloor \log_2 n \rfloor} 4^j \left(2^{\lfloor \log_2 n \rfloor-j}\right)^2 + \sum_{j=0}^{\lfloor \log_2 n \rfloor} 4^j 2^{\lfloor \log_2 n \rfloor-j}.$$ This simplifies to $$(3+\lfloor \log_2 n \rfloor) \times 4^{\lfloor \log_2 n \rfloor} - 2^{\lfloor \log_2 n \rfloor}.$$
Joining the upper and the lower bound we see that the dominant term in both is $$\lfloor \log_2 n \rfloor \times 4^{\lfloor \log_2 n \rfloor}$$ and therefore the asymptotics are $$\Theta \left(\lfloor \log_2 n \rfloor \times 4^{\lfloor \log_2 n \rfloor}\right) = \Theta\left(\log_2 n \times 2^{2\lfloor \log_2 n \rfloor} \right) \\= \Theta\left(\log n \times 2^{2 \log_2 n } \right) = \Theta\left(\log n \times n^2\right).$$ The exact result confirms precisely what the Master Theorem would have predicted.
This MSE link points to a series of similar calculations.