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

הטענה נכונה.

הוכחה: נניח בשלילה שהטענה מוטעית, ואכן $\displaystyle f(n)=\Theta (g(n))$. עפ"י ההגדרה, לכן, קיימים שני קבועים $\displaystyle c''>0$ ו$\displaystyle c'>0$ כך שלערכי $\displaystyle n$ גדולים מספיק, $\displaystyle c''\cdot g(n)\leq f(n)\leq c'\cdot g(n)$. נחלק ב$\displaystyle g(n)$ (שימו לב שאין צורך להפוך את סימני $\displaystyle \leq$), ונקבל $\displaystyle c''\leq f(n)/g(n)\leq c'$. מכללים ידועים בחדו"א, הוכחנו כעת שגבול המנה (אם הוא קיים) חסום בין $\displaystyle c''$ ל$\displaystyle c'$, בסתירה לנתון בשאלה.

באופן דומה למדי, נוכל להוכיח את המשפט הבא:

משפט: $\displaystyle f(n)$ ו$\displaystyle g(n)$ הן פונקציות חיוביות ממש, והגבול $\displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]$ קיים ושווה ל$\displaystyle lim_{n\rightarrow \infty }[f(n)/g(n)]=c$. אם $\displaystyle c=0$ אז $\displaystyle f(n)\neq \Omega (g(n))$. אם $\displaystyle c=\infty$ אז $\displaystyle f(n)\neq O(g(n))$.