Recurrence Master Theorem Question with asymptotic Upper and Lower Bounds 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?
 A: 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.
A: A direct approach: the sequence $R(k)=4^{-k}T(2^k)$ solves the recursion $$R(k)=R(k-1)+1+2^{-k},$$ hence $$R(k)=R(0)+k+1-2^{-k}=k+O(1),$$ and $$T(2^k)=k4^k+O(4^k),$$ which, if the sequence $(T(n))$ is well-behaved, yields $$T(n)\in \Theta(n^2\log n).$$ A non-asymptotic upper bound is $$R(k)\leqslant R(0)+k+1=k+1+T(1).$$ If $(T(n))$ is nondecreasing, using the smallest $k$ such that $2^k\geqslant n$, one gets
$$
T(n)\leqslant 4n^2(\log n+\log2+1+T(1)).$$ Likewise, a non-asymptotic lower bound is $$R(k)\geqslant R(0)+k=k+T(1).$$ If $(T(n))$ is nondecreasing, using the largest $k$ such that $2^k\leqslant n$, one gets
$$
T(n)\geqslant n^2(\log n+T(1)).$$
