<aside> <img src="https://super.so/icon/dark/alert-triangle.svg" alt="https://super.so/icon/dark/alert-triangle.svg" width="40px" /> These examples were done in Prof. Frid’s class during FQ 2020. If any of these shows up in a homework, let me know immediately.
</aside>
In this page, we will use:
Source: P.50 Erickson Text. $r$ and $c$ are positive integers.
Given the recurrence is $T(n) = 2T(\frac n2) + n$:
$$ \begin{array}{c:ccccccccccc:c} \text{Recursion Level}&&&&&&\text{Tree}&&&&&&\text{Work}\\\hline\\ i=0&&&&&&n&&&&&&n\\ &&&&&\swarrow&&\searrow\\ i=1&&&\dfrac n2 &&&&&&\dfrac n2&&&2(\frac n2)=n \\ &&\swarrow&&\searrow&&&&\swarrow&&\searrow\\ i=2&\dfrac n4&&&&\dfrac n4&&\dfrac n4 &&&&\dfrac n4&4(\frac n4)=n \\ \vdots &&&&&&\vdots&&&&&&\vdots\\
\end{array} $$
At every recursion level $i$, the input size is $\frac {n}{2^i}$. Then $i = \log_2n$.
Work at each level is always $n$.
Total work is:
$$ \begin{aligned} \sum^{\log_2n}{i = 0}n&=n\sum^{\log_2n}{i = 0}1\\ &=n\cdot(\log_2 n)\\ &=O(n\log n) \end{aligned} $$
Given the recurrence is $T(n) = 2T(\frac n2) + n^2$
$$ \begin{array}{c:ccccccccccc:c} \text{Recursion Level}&&&&&&\text{Tree}&&&&&&\text{Work}\\\hline\\ i=0&&&&&&n&&&&&&n^2\\ &&&&&\swarrow&&\searrow\\ i=1&&&\dfrac n2 &&&&&&\dfrac n2&&&2\left(\dfrac n2\right)^2 \\ &&\swarrow&&\searrow&&&&\swarrow&&\searrow\\ i=2&\dfrac n4&&&&\dfrac n4&&\dfrac n4 &&&&\dfrac n4&4\left(\dfrac n4\right)^2 \\ \vdots &&&&&&\vdots&&&&&&\vdots\\
\end{array} $$
At every recursion level $i$, the input size is $\frac {n}{2^i}$. Then $i = \log_2n$.
The general formula of work at each level is:
$$ 2^i\left(\frac{n}{2^i}\right)^2 $$