שאלת מבחן במבני נתונים - אוניברסיטת בר-אילן 2020 - סימון אסימפטוטי

כתונות הפוקנציות $f, g: \mathbb{N}^+ \to \mathbb{R}^+$ הוכח או הפרך סעיף א': אם $f(n) \in O(g(n)) \cup \Theta(g(n))$ אז $f(n) \in O(g(n))$ או $f(n) \in \Theta(g(n))$ סעיף ב': אם $f(n) \in \Theta(g(n))$ אז $o(f(n)) = o(g(n))$ (שיוויון קבוצות)

רמז: בסעיף א', בחנו את יחס ההכלה בין הקבוצות $O(g(n))$ ו-$\Theta(g(n))$. בסעיף ב', כדי להוכיח שוויון קבוצות, הוכיחו הכלה דו-כיוונית תוך שימוש בהגדרות הגבוליות של הסימונים האסימפטוטיים.

פתרון: סעיף א': הטענה **נכונה**. **הוכחה:** ראשית, נראה כי $\Theta(g(n)) \subseteq O(g(n))$. על פי הגדרת **סימון תטא**, $f(n) \in \Theta(g(n))$ אם ורק אם קיימים קבועים חיוביים $c_1, c_2$ ו-$n_0$ כך שלכל $n > n_0$ מתקיים: $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$ על פי הגדרת **סימון O גדול**, $f(n) \in O(g(n))$ אם ורק אם קיימים קבועים חיוביים $c$ ו-$n_0$ כך שלכל $n > n_0$ מתקיים: $0 \le f(n) \le c g(n)$ אם $f(n) \in \Theta(g(n))$, אז בפרט קיים קבוע $c_2$ כך ש-$f(n) \le c_2 g(n)$ לכל $n$ גדול מספיק. תנאי זה הוא בדיוק ההגדרה של $f(n) \in O(g(n))$ (כאשר $c=c_2$). לכן, כל פונקציה הנמצאת ב-$\Theta(g(n))$ נמצאת גם ב-$O(g(n))$, כלומר $\Theta(g(n)) \subseteq O(g(n))$. כעת נבחן את הביטוי $O(g(n)) \cup \Theta(g(n))$. מכיוון ש-$\Theta(g(n))$ היא תת-קבוצה של $O(g(n))$, האיחוד שלהן הוא פשוט הקבוצה הגדולה יותר, כלומר: $O(g(n)) \cup \Theta(g(n)) = O(g(n))$ לכן, הטענה המקורית "אם $f(n) \in O(g(n)) \cup \Theta(g(n))$ אז $f(n) \in O(g(n))$ או $f(n) \in \Theta(g(n))$" שקולה לטענה "אם $f(n) \in O(g(n))$ אז $f(n) \in O(g(n))$ או $f(n) \in \Theta(g(n))$". זוהי טענה טריוויאלית מהצורה הלוגית "אם P אז P או Q", שהיא תמיד נכונה. $\blacksquare$ סעיף ב': הטענה **נכונה**. **הוכחה:** כדי להוכיח שוויון קבוצות $o(f(n)) = o(g(n))$, עלינו להוכיח הכלה דו-כיוונית. נתון כי $f(n) \in \Theta(g(n))$, כלומר קיימים קבועים חיוביים $c_1, c_2, n_0$ כך שלכל $n > n_0$: $c_1 g(n) \le f(n) \le c_2 g(n)$ נשתמש בהגדרה הגבולית של **סימון o קטן**: $h(n) \in o(f(n))$ אם ורק אם $\lim_{n \to \infty} \frac{h(n)}{f(n)} = 0$. **כיוון ראשון: $o(f(n)) \subseteq o(g(n))$** נניח ש-$h(n) \in o(f(n))$. לפי ההגדרה, $\lim_{n \to \infty} \frac{h(n)}{f(n)} = 0$. אנו רוצים להוכיח ש-$h(n) \in o(g(n))$, כלומר ש-$\lim_{n \to \infty} \frac{h(n)}{g(n)} = 0$. נבחן את הביטוי $\frac{h(n)}{g(n)}$. מהנתון, עבור $n>n_0$ מתקיים $f(n) \le c_2 g(n)$, או $g(n) \ge \frac{f(n)}{c_2}$. לכן, עבור $n>n_0$: $0 \le \frac{h(n)}{g(n)} = \frac{h(n)}{f(n)} \cdot \frac{f(n)}{g(n)} \le \frac{h(n)}{f(n)} \cdot c_2$ כעת נפעיל גבול על אי-השוויון: $\lim_{n \to \infty} 0 \le \lim_{n \to \infty} \frac{h(n)}{g(n)} \le \lim_{n \to \infty} \left( c_2 \cdot \frac{h(n)}{f(n)} \right)$ $0 \le \lim_{n \to \infty} \frac{h(n)}{g(n)} \le c_2 \cdot \lim_{n \to \infty} \frac{h(n)}{f(n)} = c_2 \cdot 0 = 0$ לפי **כלל הסנדוויץ'**, קיבלנו ש-$\lim_{n \to \infty} \frac{h(n)}{g(n)} = 0$. לכן, $h(n) \in o(g(n))$. **כיוון שני: $o(g(n)) \subseteq o(f(n))$** נניח ש-$h(n) \in o(g(n))$. לפי ההגדרה, $\lim_{n \to \infty} \frac{h(n)}{g(n)} = 0$. אנו רוצים להוכיח ש-$h(n) \in o(f(n))$, כלומר ש-$\lim_{n \to \infty} \frac{h(n)}{f(n)} = 0$. מהנתון, עבור $n>n_0$ מתקיים $c_1 g(n) \le f(n)$, או $g(n) \le \frac{f(n)}{c_1}$. לכן, עבור $n>n_0$: $0 \le \frac{h(n)}{f(n)} = \frac{h(n)}{g(n)} \cdot \frac{g(n)}{f(n)} \le \frac{h(n)}{g(n)} \cdot \frac{1}{c_1}$ נפעיל גבול על אי-השוויון: $\lim_{n \to \infty} 0 \le \lim_{n \to \infty} \frac{h(n)}{f(n)} \le \lim_{n \to \infty} \left( \frac{1}{c_1} \cdot \frac{h(n)}{g(n)} \right)$ $0 \le \lim_{n \to \infty} \frac{h(n)}{f(n)} \le \frac{1}{c_1} \cdot \lim_{n \to \infty} \frac{h(n)}{g(n)} = \frac{1}{c_1} \cdot 0 = 0$ שוב, לפי **כלל הסנדוויץ'**, קיבלנו ש-$\lim_{n \to \infty} \frac{h(n)}{f(n)} = 0$. לכן, $h(n) \in o(f(n))$. מאחר והוכחנו הכלה בשני הכיוונים, הקבוצות שוות: $o(f(n)) = o(g(n))$. $\blacksquare$