Data-structures 1

\begin{matrix} Prove: O (n^{2}) \subseteq O (n^{3}) \\ Proof: \\ Let f (n) \in O (n^{2}) \\ f (n) \leq c \cdot n^{2} \\ Let n_{0}^{'} = m a x (n_{0}, 1) \\ f (n) \leq c \cdot n^{2} \leq c \cdot n^{3} \\ ⟹ f (n) \in O (n^{3}) ⟹ O (n^{2}) \subseteq O (n^{3}) \end{matrix}

\begin{matrix} Prove: n^{2} \log (n) + 10 n \in Ω (5 n^{2}) \\ Let n \geq 32 \\ ⟹ \log (n) \geq \log (32) = 5 \\ ⟹ n^{2} \log (n) + 10 n \geq n^{2} \log (n) \geq 5 n^{2} \\ Alternative \\ n \geq 2 ⟹ \log (n) \geq 1 \\ ⟹ n^{2} \log (n) + 10 n \geq \frac{1}{5} 5 n^{2} = n^{2} \end{matrix}

\begin{matrix} Prove: f (n) \in Ω (g (n)) ⟹ Ω (f (n)) \subseteq Ω (g (n)) \\ Proof: \\ Let f (n) \in Ω (g (n)) \\ ⟹ \forall n \geq n_{f} : f (n) \geq c_{f} g (n) \\ Let h (n) \in Ω (f (n)) \\ ⟹ \forall n \geq n_{h} : h (n) \geq c_{h} f (n) \\ ⟹ \forall n \geq m a x (n_{h}, n_{f}) : h (n) \geq c_{h} f (n) \geq c_{h} c_{f} g (n) \\ ⟹ h (n) \in Ω (g (n)) ⟹ Ω (f (n)) \subseteq Ω (g (n)) \end{matrix}

\begin{matrix} Prove: 2 n + 15 \in o (n^{2}) \\ Proof: \\ Let c > 0 \\ Let n_{0} = m a x (1, \frac{17}{c}) \\ \forall n \geq n_{0} : 2 n + 15 \leq 17 n \leq c \frac{17}{c} n \leq c n_{0} n \leq c n^{2} \\ ⟹ 2 n + 15 \in o (n^{2}) \end{matrix}

\begin{matrix} Prove: 5 n \log (n) \in ω (n) \\ Proof: \\ Let c > 0 \\ Let n_{0} = 2^{c / 5} \\ \forall n \geq n_{0} : 5 n \log (n) \geq 5 n \log (2^{c / 5}) = c n \\ ⟹ 5 n \log (n) \in ω (n) \end{matrix}

\begin{matrix} \exists lim_{n \to \infty} \frac{f (n)}{g (n)} = L \\ L = 0 ⟺ f (n) \in o (g (n)) \\ L \neq 0 \in R ⟺ f (n) \in Θ (g (n)) \\ L = \infty ⟹ f (n) \in ω (g (n)) \\ Proof for L = 0 : \\ ⟹ \forall ε > 0 : \exists n_{0} \in N_{0} : \forall n \geq n_{0} : \frac{f (n)}{g (n)} < ε \\ g (n) > 0 ⟹ f (n) < ε g (n) ⟹ f (n) \leq ε g (n) \end{matrix}

\begin{matrix} Prove: \log (n!) \in Θ (n \log (n)) \\ Proof: \\ \log (n!) \leq \log (n^{n}) = n \log (n) \\ \frac{n}{2} \log (\frac{n}{2}) = \frac{1}{2} n (\log (n) - \log (2)) = \frac{1}{2} n \log (n) - \frac{1}{2} n \\ n \geq 4 ⟹ \log (n) \geq 2 ⟹ \frac{\log (n)}{2} \geq 1 \\ ⟹ \log ({\frac{n}{2}}^{n / 2}) = \frac{1}{2} n \log (n) - \frac{1}{2} n \geq \frac{1}{2} n \log (n) - \frac{1}{4} n \log (n) = \frac{1}{2} n \log (n) \\ ⟹ \frac{1}{2} n \log (n) \leq \log ({(\frac{n}{2})}^{n / 2}) \leq \log (n!) \leq n \log (n) \\ ⟹ \log (n!) \in Θ (n \log (n)) \end{matrix}