The number of blit operations can be expressed as: \[T(n) = \begin{cases} 0, & n=1\\ 5 + 4 T(\frac{n}{2}), & n > 1 \end{cases}\]
For \(n = 2^x\) we try the algorithm for incremental sizes of \(x\) to find a pattern for how the algorithm behaves.
\[\begin{aligned} T(2^0) &= 0\\ T(2^1) &= 5\\ T(2^2) &= 5 + 5 \cdot 2^2\\ T(2^3) &= 5 + 5 \cdot 2^2 + 5 \cdot 2^4\\ T(2^4) &= 5 + 5 \cdot 2^2 + 5 \cdot 2^4 + 5 \cdot 2^6\\ T(2^5) &= 5 + 5 \cdot 2^2 + 5 \cdot 2^4 + 5 \cdot 2^6 + 5 \cdot 2^8\end{aligned}\]
We hypothesise that: \[\begin{split} T(2^n) &= \sum_{i = 0}^{n-1} \left[5 \cdot 4^i\right] = 5\sum_{i = 0}^{n-1} \left[4^i\right]\\ &= 5\frac{1 - 4^n}{1 - 4} = \frac{5 - 5 \cdot 4^n}{-3}\\ &= \frac{5 \cdot 4^n - 5}{3} \end{split}\]
Proof by induction:
This holds for the base cases \(n \in \{0, 1, 2, 3, 4\}\) (verifying this is left as an exercise for the reader).
Now we show that the above expression is true for all \(n \geq 0\). Given that \(T(2^n) = \frac{5 \cdot 4^n - 5}{3}\) is true for some \(n\), we need to show that \(T(2^{n+1}) = \frac{5 \cdot 4^{n+1} - 5}{3}\). Using the above definition of \(T(n)\), we get: \[\begin{split} T(2^{n+1}) &= 5 + 4\frac{5 \cdot 4^n - 5}{3}\\ &= 5 + \frac{5 \cdot 4^{n+1} - 5 \cdot 4}{3}\\ &= \frac{5 \cdot 4^{n+1} + 5 \cdot 3 - 5 \cdot 4}{3}\\ &= \frac{5 \cdot 4^{n+1} - 5}{3} \end{split}\] Q.E.D.
This gives us that: \[\begin{split} T(n) &= \frac{5 \cdot 4^{\log(n)} - 5}{3}\\ &= \frac{5(2^2)^{\log(n)} - 5}{3}\\ &= \frac{5n^2 - 5}{3}\\ T(n) &\in \mathcal{O}(n^2) \end{split}\]