Recurrence Master Theorem Question with asymptotic Upper and Lower Bounds

Question

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?

Answer 1

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

Answer 2

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.