נוספו 1,968 בתים,
11:01, 29 ביוני 2013 [[תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר|חזרה לקישורים לתקצירים]]
==דוגמה==
אם אנו חושדים שזמן הריצה <math>t</math> כתלות ב־<math>n</math> פרופורציוני ל־<math>n^r</math>:
<div align="left">
<math>t\propto n^r</math> <BR>
<math>\Downarrow</math> <BR>
<math>t=cn^r</math> <BR>
<math>\ln t=\ln c+r\ln n</math> <BR>
<div align="right">
לכן <math>\ln t</math> כתלות ב־<math>\ln n</math> הינו קו ישר ששיפועו <math>r</math>, וכך ניתן למצוא את <math>\ln c</math> כחיתוך עם ציר y.
==מספר הגדרות ודוגמות==
<math>f\left ( n \right )=\Theta\left ( g\left ( n \right ) \right )</math> אם <math>\forall n, A\cdot g\left ( n \right )\leq f\left ( n \right )\leq B\cdot g\left ( n \right )</math>.
<math>f\left ( n \right )=O \left ( g\left ( n \right ) \right )</math> אם <math>\forall n, f\left ( n \right )\leq B\cdot g\left ( n \right )</math>.
''דוגמה:''
<math>e^x=1+x+\frac{x^2}{2}+...=\sum_{n=0}^\infty\frac{x^n}{n!}</math>, לכן <math>e^x=1+x+\frac{x^2}{2}+O(x^3)</math>. <BR>
באופן מדויק: <math>e^x=1+x+\frac{x^2}{2}+\frac{(x^*)^3}{6}</math> כאשר <math>|x^*|<|x|</math>, ולכן <math>\frac{(x^*)^3}{6}\leq\frac{1}{6} x^3</math>.
''דוגמה נוספת:''
בחיפוש בינארי מבוצעות <math>\left \lceil \log_2 n\right \rceil</math> פעולות, ולכן היעילות הינה <math>\left \lceil \log_2 n\right \rceil=O(\log_2 n)=O(\ln n)</math>.
<math>f\left ( n \right )=o\left ( g\left ( n \right ) \right )</math> אם <math>\lim_{n\rightarrow\infty}\frac{f\left ( n \right )}{g\left ( n \right )}=0</math>.
''דוגמה:''
<math>e^{-x}=o\left ( x^n \right )</math> כי <math>\lim_{x\rightarrow\infty}\frac{e^{-x}}{x^n}=0</math>
''דוגמה נוספת:''
<math>\ln x=o\left ( x \right )</math> וגם <math>\ln x=O\left ( x \right )</math>.