From fcf4d85007dcfcbdc6220331f5f9d9ba31f6ae67 Mon Sep 17 00:00:00 2001
From: Yigit Sever
Date: Sat, 7 Nov 2020 04:27:52 +0300
Subject: Last part of the question

Only last part of 4 left
---
 main.tex | 51 +++++++++++++++++++++++++++++++++++----------------
 1 file changed, 35 insertions(+), 16 deletions(-)

diff --git a/main.tex b/main.tex
index 8002998..fe20d1f 100644
--- a/main.tex
+++ b/main.tex
@@ -552,12 +552,12 @@ For the right hand side; we can start by picking $n_{0} = 1$ and $c = 1$ in the
 
 In order to prove the right hand side of the inequality; we can pick $c_2 > 2$ which equals;
 
-\begin{eqnarray*}%
+\begin{align*}%
     \label{eq:c2gt2}
-    f(n) + g(n) \le 2 \cdot f(n) \\
-    \cancel{f(n)} + g(n) \le \cancel{2 \cdot} f(n) \\
-    g(n) \le f(n)
-\end{eqnarray*}
+    f(n) + g(n) &\le 2 \cdot f(n) \\
+    \cancel{f(n)} + g(n) &\le \cancel{2 \cdot} f(n) \\
+    g(n) &\le f(n)
+\end{align*}
 
 Which we proved above using Equation~\ref{eq:a_little_o}. This conjecture is \emph{true}.
 
@@ -589,8 +589,7 @@ Which we proved above using Equation~\ref{eq:a_little_o}. This conjecture is \em
 
 Hence $f(n) = \mathcal{O}(n^{2})$ and $H=2$.
 
-% TODO: reread proof, strengthen? <06-11-20, yigit> %
-(2)$L=2$. We can pick the constant $c = \frac{1}{2}$ and write the Big-$\Omega$ notation;
+(2) $L=2$. We can pick the constant $c = \frac{1}{2}$ and write the Big-$\Omega$ notation;
 
 \begin{gather*}
     c > 0 ~ \text{and} ~ n_{0} \ge 0 \\
@@ -601,21 +600,41 @@ Hence $f(n) = \mathcal{O}(n^{2})$ and $H=2$.
 
 Does a $L>2$ work? Pick any $\ell > 2$;
 
-\begin{gather*}
-    c > 0 ~ \text{and} ~ n_{0} \ge 0 \\
-    \frac{n(n+1)}{2} \ge \frac{1}{2} n^{\ell} \\
-    \frac{n(n+1)}{\cancel{2}} \ge \frac{1}{\cancel{2}} n^{\ell} \\
-    n(n+1) \ge n^{\ell} \\
-    n+1 \ge n^{\ell - 1} \\
-    1 \ge n(n^{\ell - 2} - 1)
-\end{gather*}
+\begin{align*}
+    c > 0 ~ \text{and} ~ n_{0} &\ge 0 \\
+    \frac{n(n+1)}{2} &\ge \frac{1}{2} n^{\ell} \\
+    \frac{n(n+1)}{\cancel{2}} &\ge \frac{1}{\cancel{2}} n^{\ell} \\
+    n(n+1) &\ge n^{\ell} \\
+    n+1 &\ge n^{\ell - 1} \\
+    1 &\ge n(n^{\ell - 2} - 1)
+\end{align*}
 
-The final equation does not hold $n>1$ so $L>2$ cannot be true.
+The final equation does not hold for $n>1$ or the assumed $\ell > 2$ so $L>2$ cannot be true.
 
 \begin{info}[]
     $f(n) = \sum^{\lceil{\log{n}}\rceil}_{k=0} \frac{n}{2^{k}}$
 \end{info}
 
+It's beneficial to unpack the infinite sum beforehand;
+
+\begin{align*}
+    f(n) &= \sum^{\lceil{\log{n}}\rceil}_{k=0} \frac{n}{2^{k}}\\
+    &= \frac{n}{2^{0}} + \frac{n}{2^{1}} + \frac{n}{2^{2}} + \dots + \frac{n}{2^{\lceil{\log{n}}\rceil}} \\
+    &= n \Big(1 + \frac{1}{2^{1}} + \frac{1}{2^{2}} + \dots + \frac{1}{2^{\lceil{\log{n}}\rceil}} \Big) \\
+\end{align*}
+
+The infinite sum approaches 1 as $\lceil{\log n\rceil} \rightarrow \infty$, giving us;
+
+\begin{equation*}
+    f(n) = 2 \cdot n \\
+\end{equation*}
+
+Finally, $H = L = 1$ since $f(n)$ is $\Theta(n)$. Borrowing the Big-$\Theta$ notation from Equation~\ref{eq:a_big_theta} for $c_1 = 1$ and $c_2 = 2$;
+
+\begin{equation*}
+    n \le f(n) \le 2n
+\end{equation*}
+
 \begin{info}[]
     $f(n) = n(\log n)^{2}$
 \end{info}
-- 
cgit v1.2.3-70-g09d2