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

ראשית נראה ש$\displaystyle f(n)=O(g(n))$.

הוכחה: $\displaystyle \lim _{n\rightarrow \infty }{\frac {f(n)}{g(n)}}=$
$\displaystyle \lim _{n\rightarrow \infty }{\frac {n+c_{1}n\log ^{2}(n)}{n+c_{2}n^{2}}}=$
$\displaystyle \lim _{n\rightarrow \infty }{\frac {{\frac {1}{n}}+c_{1}{\frac {1}{n}}\log ^{2}(n)}{{\frac {1}{n}}+c_{2}}}=$
$\displaystyle 0$

הטענה נובעת, לכן, מכלל הגבולות בסדרי גדילה.

כעת נראה כי $\displaystyle g(n)\neq O(f(n))$

הוכחה: נניח בשלילה כי $\displaystyle g(n)=O(f(n))$. אז קיים $\displaystyle c>0$ כך שעבור ערכי $\displaystyle n$ גדולים מספיק, $\displaystyle g(n)\leq c\cdot f(n)$.

נחלק את שני האגפים ב$\displaystyle f(n)$ (נזכר שהוא חיובי), ונקבל $\displaystyle {\frac {g(n)}{f(n)}}\leq c$ עבור ערכי $\displaystyle n$ גדולים מספיק.

ניקח גבול של שני האגפים, ונקבל $\displaystyle \lim _{n\rightarrow \infty }{\frac {g(n)}{f(n)}}\leq \lim _{n\rightarrow \infty }c=c$.

אבל במקרה כאן, קל לראות שהגבול שואף לאינסוף, ולכן אין קבוע שחוסם אותו מלמעלה.