מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה/תרגילים/הכוון השני לכללי הגבולות/תשובה

נבנה את הפונקציה $\displaystyle g(n)$ כך:

1. ראשית נקבע צמדים של נקודות.
   1. נקבע $\displaystyle n_{0}=1$,‏ ו$\displaystyle n_{1}$ כנקודה הקטנה ביותר בה $\displaystyle f(n_{1})\geq 2\cdot f(n_{0})$ ‏(חייבת להיות נקודה כזו, כי $\displaystyle f(n)$ שואפת לאינסוף)‏‏.
   2. נקבע $\displaystyle n_{2}=n_{1}+1$,‏ ו$\displaystyle n_{3}$ כנקודה הקטנה ביותר בה $\displaystyle f(n_{3})\geq 2\cdot f(n_{2})$ (חייבת להיות נקודה כזו, כי $\displaystyle f(n)$ שואפת לאינסוף)‏.
   3. נמשיך כך הלאה: נקבע $\displaystyle n_{4}=n_{3}+1$,‏ ו$\displaystyle n_{5}$ כנקודה הקטנה ביותר בה $\displaystyle f(n_{5})\geq 2\cdot f(n_{4}$) (חייבת להיות נקודה כזו, כי $\displaystyle f(n)$ שואפת לאינסוף)‏, וכולי.
2. כעת נגדיר את $\displaystyle g(n)$ בעזרת הזוגות:
   1. עבור $\displaystyle n_{0}\leq n<n_{1}$,‏ $\displaystyle g(n)=f(n_{0})$;‏ $\displaystyle g(n_{1})=f(n_{1})/2$.
   2. עבור $\displaystyle n_{2}\leq n<n_{3}$,‏ $\displaystyle g(n)=f(n_{2})$;‏ $\displaystyle g(n_{3})=f(n_{3})/2$.
   3. עבור $\displaystyle n_{4}\leq n<n_{5}$,‏ $\displaystyle g(n)=f(n_{4})$;‏ $\displaystyle g(n_{5})=f(n_{5})/2$. נמשיך כך הלאה והלאה.מהבניה קל לראות את הדברים הבאים:
   4. $\displaystyle g(n)$ פונקציה מונוטונית עולה.
   5. בכל נקודה ונקודה, $\displaystyle g(n)$ נמצאת בין $\displaystyle f(n)$ ל$\displaystyle f(n)/2$. לכן $\displaystyle g(n)=\Theta (f(n))$ בהכרח.
   6. יש אינסוף נקודות בהן $\displaystyle f(n)=g(n)$, אבל גם אינסוף נקודות בהן $\displaystyle g(n)=f(n)/2$, ולכן לא ייתכן שהגבול $\displaystyle f(n)/g(n)$ קיים.

כדאי לדעת: לכאורה אפשר לבנות פונקציה $\displaystyle g_{1}(n)$ פשוטה הרבה יותר מהמוצגת כאן, לדוגמה: $\displaystyle g_{1}(n)=f(n)$ אם $\displaystyle n$ זוגי. $\displaystyle g_{1}(n)=f(n)/2$ אם $\displaystyle n$ אי זוגי. עם זאת, אמרנו בתחילת הדף על סדרי גדילה שנתמקד בקורס בפונקציות מונוטוניות לא יורדות, והפונקציה $\displaystyle g(n)$ שנבנתה כאן אכן מונוטונית לא יורדת.