this is for holding javascript data
Mazdak Farrokhzad edited a) Number of blits.tex
about 10 years ago
Commit id: c525e36f8e1b837d595d8b7029ac0fd2af6f64ed
deletions | additions
diff --git a/a) Number of blits.tex b/a) Number of blits.tex
index 92c427a..97006de 100644
--- a/a) Number of blits.tex
+++ b/a) Number of blits.tex
...
\begin{verbatim} \section{Number of blits}
T(n) = The recursive algorithm can be expressed as having the cost:
\[T(n) &= (n = 2) ? 5 : 5 + 4 T(n /
2) 2)\]
T(2^1) For $n =
5 2^x$ we try the algorithm for incremental sizes of $x$ to find a pattern for how the algorithm behaves.
\begin{subequation}
\begin{split}
T(2^1) &= 5\\
T(2^2)
= &= 5 + 5 *
2^2 2^2\\
T(2^3)
= &= 5 + 5 * 2^2 + 5 *
2^4 2^4\\
T(2^4)
= &= 5 + 5 * 2^2 + 5 * 2^4 + 5 *
2^6 2^6\\
T(2^5)
= &= 5 + 5 * 2^2 + 5 * 2^4 + 5 * 2^6 + 5 * 2^8
\end{split}
\end{equation}
Given that:
T(2^n) = sum(5 * 4^i, i = 0, n-1) = 5 sum(4^i, i = 0, n-1) = 5 * ((1 - 4^n)/(1 - 4)) = (5 - 5 * 4^n)/(-3) = (5 * 4^n - 5) / 3
...
T(2^(n+1)) = 5 + 4 ((5 * 4^n - 5) / 3) = 5 + (5 * 4^(n+1) - 4*5) / 3 = (5 * 4^(n+1) + 3 * 5 - 4 * 5) / 3 = (5 * 4^(n+1) - 5) / 3
T(n) = (5 * 4^log(n) - 5) / 3 = (5 * (2^2)^log(n) - 5) / 3 = (5 * n^2 - 5) / 3
T(n) = O(n^2)
\end{verbatim}