שינויים

*<math>f(n)=O(f(n))</math>. כנ"ל עבור <math>\Theta,\Omega</math>. (זהירות: <math>f(n)\neq o(f(n))</math>!)*<math>f(n)=O(g(n))</math> אם ורק אם <math>g(n)=\Omega(f(n))</math>.* <math>O(f(n))+O(g(n))=O(f(n)+g(n))</math>. כנ"ל עבור <math>\Theta,\Omega</math>.* <math>O(f(n))\cdot O(g(n))=O(f(n)g(n))</math>. כנ"ל עבור <math>\Theta, \Omega</math>.* <math>O(f(n))^\alpha=O(f(n)^\alpha)</math> לכל <math>\alpha>0</math>. כנ"ל עבור <math>\Theta,\Omega</math>.* היחס <math>f(n)=O(g(n))</math> הוא טרנזיטיבי. (ניסוח אחר: <math>O(O(f(n)))=O(f(n))</math>.) כנ"ל עבור <math>\Theta,\Omega</math>.* היחס <math>f(n)=\Theta(g(n))</math> הוא יחס שקילות.* <math>f(n)+o(f(n))=\Theta(f(n))</math>.  == יחסים בין פונקציות נפוצות == * לכל <math>a,b,c>0</math> ו-<math>d>1</math> ממשיים מתקיים <math>\dots\ll (\ln\ln n)^a\ll (\ln n)^b\ll n^c\ll d^n\ll n!\ll n^n</math>.* לכל <math>a<b</math> ממשיים <math>n^a\ll n^b</math>. * לכל <math>1\leq a<b</math> ממשיים <math>a^n\ll b^n</math>.