aboutsummaryrefslogtreecommitdiffstats
path: root/main.tex
diff options
context:
space:
mode:
Diffstat (limited to 'main.tex')
-rw-r--r--main.tex10
1 files changed, 6 insertions, 4 deletions
diff --git a/main.tex b/main.tex
index dcb7980..a67b175 100644
--- a/main.tex
+++ b/main.tex
@@ -131,7 +131,7 @@ $S'$ could not have occurred since men propose in accordance to their preference
131For a proposer agnostic formation, arrange the preference lists of colleges and students as follows; 131For a proposer agnostic formation, arrange the preference lists of colleges and students as follows;
132 132
133\begin{gather*}% 133\begin{gather*}%
134 \label{eq:student_prefs} 134 \label{eq:college_prefs}
135 C_{1} \rightarrow \left\{ S_{1}, S_{n}, S_{n-1}, \dots, S_{2} \right\} \\ 135 C_{1} \rightarrow \left\{ S_{1}, S_{n}, S_{n-1}, \dots, S_{2} \right\} \\
136 C_{2} \rightarrow \left\{ S_{2}, S_{n}, S_{n-1}, \dots, S_{3} \right\} \\ 136 C_{2} \rightarrow \left\{ S_{2}, S_{n}, S_{n-1}, \dots, S_{3} \right\} \\
137 \dots \\ 137 \dots \\
@@ -517,6 +517,8 @@ For $c > 1$ and $n_{0} > 1$;
517 517
518For $f(n) \ge 1$. The conjecture is true for asymptotically positive function $f(n)$ but does not hold for an $f(n) < 1$. 518For $f(n) \ge 1$. The conjecture is true for asymptotically positive function $f(n)$ but does not hold for an $f(n) < 1$.
519 519
520\pagebreak
521
520\begin{info}[] 522\begin{info}[]
521 $f(n) + o(f(n)) = \Theta(f(n))$ 523 $f(n) + o(f(n)) = \Theta(f(n))$
522\end{info} 524\end{info}
@@ -629,7 +631,7 @@ The infinite sum approaches 1 as $\lceil{\log n\rceil} \rightarrow \infty$, givi
629 f(n) = 2 \cdot n \\ 631 f(n) = 2 \cdot n \\
630\end{equation*} 632\end{equation*}
631 633
632Finally, $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$; 634(1,2) 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$;
633 635
634\begin{equation*} 636\begin{equation*}
635 n \le f(n) \le 2n 637 n \le f(n) \le 2n
@@ -646,11 +648,11 @@ Finally, $H = L = 1$ since $f(n)$ is $\Theta(n)$. Borrowing the Big-$\Theta$ not
646 n^{\frac{1}{2}} \quad v.s. \quad \log{n} 648 n^{\frac{1}{2}} \quad v.s. \quad \log{n}
647\end{align*} 649\end{align*}
648 650
649From the lectures we know that $\log{n}$ is $\mathcal{O}(n^{d})$ for all $d$. 651(1) From the lectures we know that $\log{n}$ is $\mathcal{O}(n^{d})$ for all $d$.
650 652
651If $\log{n}$ is $\mathcal{O}(n^{\frac{1}{2}})$ then $n(\log{n})^{2}$ is $\mathcal{O}(n^{2})$. $H=2$. 653If $\log{n}$ is $\mathcal{O}(n^{\frac{1}{2}})$ then $n(\log{n})^{2}$ is $\mathcal{O}(n^{2})$. $H=2$.
652 654
653For $L$; we know that $f(n) = n(\log{n})^{2} > n^{1}$ but $n(\log{n})^{2} < n^{2}$ hence L = 1$. 655(2) For $L$; we know that $f(n) = n(\log{n})^{2} > n^{1}$ but $n(\log{n})^{2} < n^{2}$ hence $L = 1$.
654 656
655% 1}}} % 657% 1}}} %
656 658