From d7bee95a5538e10ac13dd8f91aa773e3a776bff5 Mon Sep 17 00:00:00 2001
From: Yigit Sever
Date: Sat, 7 Nov 2020 03:51:35 +0300
Subject: Answer 4.a done

---
 main.tex | 32 ++++++++++++++++----------------
 1 file changed, 16 insertions(+), 16 deletions(-)

(limited to 'main.tex')

diff --git a/main.tex b/main.tex
index 21235f0..8002998 100644
--- a/main.tex
+++ b/main.tex
@@ -461,7 +461,7 @@ And when the limit of two functions $f, g$ converge to some constant $c$, then $
 \section{Big $\mathcal{O}$ and $\Omega$}%
 \label{sec:big_o_and_omega_}
 
-% question a ALMOST DONE {{{1 %
+% question a ✅ {{{1 %
 
 \begin{question}
     Let $f(n)$ and $g(n)$ be asymptotically positive functions. Prove or disprove the following conjectures.
@@ -484,7 +484,7 @@ If we rearrange the right hand side of the Proposition~\ref{eq:a_bigo};
     0 \le \frac{1}{c} f(n) \le g(n) \\
 \end{equation*}
 
-or simply,
+Or simply,
 
 \begin{equation}
     \label{eq:a_bio_rearranged}
@@ -503,21 +503,11 @@ Has to be true, yet from Equation~\ref{eq:a_bio_rearranged} we know that $f(n)$
     $f(n) = \mathcal{O}((f(n))^{2})$
 \end{info}
 
-% TODO: this is dumb ask this <05-11-20, yigit> %
-
 % https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/assignments/ps1sol.pdf
 
-The question text states that $f(n)$ is a positive function.
-
-By the definition of Big $\mathcal{O}$ notation, we have;
+We can reuse the definition of Big $\mathcal{O}$ notation given in Equation~\ref{eq:a_bigo}, and using the question text, we have;
 
-\begin{equation*}%
-    \exists ~ c > 0 \quad \text{and} \quad n_{0} \ge 0 \mid ~ 0 \le f(n) \le c \cdot g(n) \quad \forall n \ge n_{0}
-\end{equation*}
-
-For $c > 1$ and $n_{0} > 1$ we have;
-
-% TODO: this makes zero sense? <06-11-20, yigit> %
+For $c > 1$ and $n_{0} > 1$;
 
 \begin{align*}%
     f(n) &\le f(n)^{2} \quad \forall n \ge n_{0} \\
@@ -525,6 +515,8 @@ For $c > 1$ and $n_{0} > 1$ we have;
     f(n) &\le c\cdot g(n) \quad \forall n \ge n_{0}
 \end{align*}
 
+For $f(n) \ge 1$. The conjecture is true for asymptotically positive function $f(n)$ but does not hold for an $f(n) < 1$.
+
 \begin{info}[]
     $f(n) + o(f(n)) = \Theta(f(n))$
 \end{info}
@@ -556,10 +548,18 @@ It's trivial to pick $c_1 < 1$ to deal with the left hand side of the inequality
     f(n) \le f(n) + g(n)
 \end{equation*}
 
-For the right hand side, we can pick $n_{0} = 1$ and $c = 1$ in the Equation~\ref{eq:a_little_o}; keeping $g(n) < f(n)$.
+For the right hand side; we can start by picking $n_{0} = 1$ and $c = 1$ in the Equation~\ref{eq:a_little_o}; keeping $g(n)$ strictly smaller than  $f(n)$.
+
+In order to prove the right hand side of the inequality; we can pick $c_2 > 2$ which equals;
 
-Finally, picking $c2 > 2$ proves the conjecture.
+\begin{eqnarray*}%
+    \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*}
 
+Which we proved above using Equation~\ref{eq:a_little_o}. This conjecture is \emph{true}.
 
 % 1}}} %
 
-- 
cgit v1.2.3-70-g09d2