<aside> 📌 SUMMARY: When performing recurrences, we get a geometric series that behaves differently based on the fractional terms within. 3 cases can occur whether $a >b$, $a=b$ or $a < b$
</aside>
Examples for divide and conquer. Note that for the different algorithms, we may have different numbers of sub-problems to solve.
At each step, we substitute the original equation with an $\frac{n}{2^i}$ term, where $i$ is the current step number. After we do this long enough, we get a geometric relation that gives us the runtime.
$T(n) = 4T(\frac{n}{2}) + O(n)$
$$ \begin{aligned} T(n) &\leq cn + 4T\left(\frac{n}{2}\right) \\ &\leq cn + 4\left[4T\left(\frac{n}{2^2}\right) + c\frac{n}{2}\right] ,\space\text{substitute} \space n \space \text{with} \space \frac{n}{2} \space \text{in 2nd part}\space T(\frac{n}{2}) \rightarrow T(\frac{n}{2}) \leq c(\frac{n}{2}) + 4T(\frac{n}{2^2})\\ &= cn\left(1 + \frac{4}{2}\right) + 4^2T\left(\frac{n}{2^2}\right), \space \text{factor out $cn$} \\ &\leq cn\left(1 + \frac{4}{2}\right) + 4^2\left[4T\left(\frac{n}{2^3}\right) + c\left(\frac{n}{2^2}\right)\right], \space \text{substitute $n$ with} \space\frac{n}{4} \space\text{in 2nd part}, \rightarrow T(\frac{n}{4}) \leq c(\frac{n}{4})+4T(\frac{n}{2^3}) \\ &= cn\left(1 + \frac{4}{2} + \left(\frac{4}{2}\right)^2\right) + 4^3T\left(\frac{n}{2^3}\right), \text{factor out $cn$} \\ &= ... \end{aligned} $$
Through expanding out, we get a geometric series which stops at a base case when $\frac{n}{2^i} = 1$, $i = \log_2n$. From each individual term’s runtime, we get the eventual runtime of $O(n^2)$.
<aside> 📌 SUMMARY: When doing integer multiplications, we can divide into subproblems by splitting the inputs into halves, then running the same multiplication algorithm on those halves This leads us to 4 subproblems of the form $(a+bi)(c+di) = ac-bd+(bc+ad)i$ → we have 4 multiplications However using an idea from Gauss, we can reduce it to 3 subproblems $(bc+ad)=(a+b)(c+d)-\blue{ac}-\blue{bd}$ → we only need 3 multiplications here
</aside>