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

נניח ש$\displaystyle f(n)$ פולינום מדרגה $\displaystyle f$, ו$\displaystyle g(n)$ פולינום מדרגה $\displaystyle g$. אז:

• $\displaystyle f<g\Rightarrow f(n)=O(g(n))$
• $\displaystyle f=g\Rightarrow f(n)=\Theta (g(n))$
• $\displaystyle f>g\Rightarrow f(n)=\Omega (g(n))$

במילים אחרות, זה נקבע עפ"י יחס החזקות הגבוהות ביותר. קל להוכיח טענות אלו ע"י כללי הגבולות שראינו.