diff options
Diffstat (limited to 'main.tex')
-rw-r--r-- | main.tex | 10 |
1 files changed, 6 insertions, 4 deletions
@@ -131,7 +131,7 @@ $S'$ could not have occurred since men propose in accordance to their preference | |||
131 | For a proposer agnostic formation, arrange the preference lists of colleges and students as follows; | 131 | For 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 | ||
518 | For $f(n) \ge 1$. The conjecture is true for asymptotically positive function $f(n)$ but does not hold for an $f(n) < 1$. | 518 | For $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 | ||
632 | 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$; | 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 | ||
649 | From 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 | ||
651 | If $\log{n}$ is $\mathcal{O}(n^{\frac{1}{2}})$ then $n(\log{n})^{2}$ is $\mathcal{O}(n^{2})$. $H=2$. | 653 | If $\log{n}$ is $\mathcal{O}(n^{\frac{1}{2}})$ then $n(\log{n})^{2}$ is $\mathcal{O}(n^{2})$. $H=2$. |
652 | 654 | ||
653 | For $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 | ||