From ca2af8e5bf4f6523dde2f56a17426a01e40f7eba Mon Sep 17 00:00:00 2001
From: Yigit Sever
Date: Fri, 6 Nov 2020 03:02:23 +0300
Subject: Typeset the answer of 3rd question

---
 main.tex | 65 +++++++++++++++++++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 56 insertions(+), 9 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index c885da8..2676213 100644
--- a/main.tex
+++ b/main.tex
@@ -212,12 +212,57 @@ Matching z with c (a)
 \section{Asymptotics}%
 \label{sec:asymptotics}
 
-% asymptotics TODO {{{1 %
+% asymptotics ✅ {{{1 %
 
 \begin{question}
-    What is the running time of this algorithm as a function of n? Specify a function f such that the running time of the algorithm is $\Theta(f(n))$.
+    What is the running time of this algorithm as a function of $n$? Specify a function $f$ such that the running time of the algorithm is $\Theta(f(n))$.
 \end{question}
 
+{\centering
+    \begin{minipage}{.7\linewidth}
+        \begin{algorithm}[H]
+            \For(\tcc*[f]{outer loop}){$i = 2$; $i < n$; $i += 1$ }{
+                \For(\tcc*[f]{inner loop}){$j=1$; $j < n$; $j * = i$}{
+                    Some $\Theta(1)$ operation\;
+                }
+            }
+            \caption{Equivalent algorithm to one given in Question 3, edited for brevity}%
+            \label{alg:question_3}
+\end{algorithm}
+\end{minipage}
+\par
+}
+
+The outer loop runs in linear time $\mathcal{O}(n)$ whereas the inner loop requires some deconstruction;
+
+Take the first iteration of the inner loop, $i = 2$ and $j$ is initialized at $1$.
+
+\begin{align*}%
+    \label{eq:3_iterations}
+    1^{\text{st}} ~ \text{iteration} &\rightarrow  j = j * i \implies  j = 2 \\
+    2^{\text{nd}} ~ \text{iteration} &\rightarrow  j = 4 \\
+    3^{\text{rd}} ~ \text{iteration} &\rightarrow  j = 8 \\
+    \dots \\
+    m^{\text{th}} ~ \text{iteration} &\rightarrow  j = i^{m} < n \\
+\end{align*}
+
+$m$ is the last iteration of the inner loop because it hit the stopping condition $i^{m} < n$.
+Using the Equations above we can find the running time for the inner loop to hit stopping condition;
+
+\begin{gather*}
+    i^{m} < n \\
+    m < \log_{i} n
+\end{gather*}
+
+In other words, the inner loop has a running time in the order of $\mathcal{O}(\log{n})$. By the product property of $\mathcal{O}$-notation we have the running time of $\mathcal{O}(n\log_{a}{n}), a > 1$ for the entire algorithm. The base $a$ is useful to answer the rest of the question;
+
+We can specify a function $f$ such as $f = n \log_{b}(n)$ where $b > 1$. From the course slides;
+
+\begin{equation*}
+    \lim_{n \to \infty}\frac{n\log_{a}{n}}{n \log_{b}{n}} = c
+\end{equation*}
+
+And when the limit of two functions $f, g$ converge to some constant $c$, then $f(n) = \Theta(g(n))$.
 
 % 1}}} %
 
@@ -280,11 +325,13 @@ By the definition of Big $\mathcal{O}$ notation, we have;
 
 For $c > 1$ and $n_{0} > 1$ we have;
 
-\begin{eqnarray*}%
-    f(n) \le f(n)^{2} \quad \forall n \ge n_{0} \\
-    g(n) = f(n)^{2} \\
-    f(n) \le c\cdot g(n) \quad \forall n \ge n_{0}
-\end{eqnarray*}
+% TODO: this makes zero sense? <06-11-20, yigit> %
+
+\begin{align*}%
+    f(n) &\le f(n)^{2} \quad \forall n \ge n_{0} \\
+    \text{take} ~ g(n) &= f(n)^{2} \\
+    f(n) &\le c\cdot g(n) \quad \forall n \ge n_{0}
+\end{align*}
 
 \begin{info}[]
     $f(n) + o(f(n)) = \Theta(f(n))$
@@ -337,11 +384,11 @@ Otherwise, indicate that H or L do not exist.
 \end{info}
 
 \begin{info}[]
-    $f(n) = \sum^{\lceil{log n}\rceil}_{k=0} \frac{n}{2^{k}}$
+    $f(n) = \sum^{\lceil{\log{n}}\rceil}_{k=0} \frac{n}{2^{k}}$
 \end{info}
 
 \begin{info}[]
-    $f(n) = n(log n)^{2}$
+    $f(n) = n(\log n)^{2}$
 \end{info}
 
 
-- 
cgit v1.2.3-70-g09d2