שינויים

1. \begin{enumerate}\item מסמנים $a_n=O(b_n) , n\to \infty $ ("הסדרה $a_n$ היא O גדול של $b_n$") אם מתקיים $$\exists_{M>0} \exists_{n_0} \forall_{n>n_0} 0\leq a_n \leq M\cdot b_n $ . $הסימן הזה חוזר המון במחשבים כשבודקים יעילות של אלגוריתמים. לדוגמה אלגוריתם שמקבל קלט $n$ מסוים ועושה $a_n=2n+4 $ פעולות אומרים שהיעילות שלו היא מסדר $O(n)$ משום שאכן $ 2n+4=O(n) , n\to \infty $ , כי אם ניקח $M=3 $ אז אכן ממקום מסוים והלאה, $2n+4\leq 3n $ .

2. \item מסמנים $a_n=O^* (b_n) , n\to \infty $ אם מתקיים $$\exists_{M,m>0} \exists_{n_0} \forall_{n>n_0} m_0\cdot b_n\leq a_n \leq M\cdot b_n $ . $שימו לב שאם $a_n=O^* (b_n) $ אז $a_n=O(b_n) $ וגם $b_n=O^* (a_n) $ (כל אלה כמובן כש- $n\to \infty$ משום שאלה סדרות, אבל בפונקציות זה גם יתקיים סביב נקודות)

3. \item נניח $b_n\neq 0 $ אז אפשר להגדיר את הסימן $a_n=o(b_n) ,n\to\infty $ ("O הסדרה $a_n$ היא o קטןשל $b_n$") אם $$\lim_{n\to \infty} \frac{a_n}{b_n} = 0 $ . $אפשר לחשוב על זה אינטואיטיבית של $b_n$ גדל הרבה הרבה יותר מהר מ-$a_n$ או ש- $a_n$ אפסי לעומת $b_n$, הסימן הזה יחזור הרבה כשנדבר על נגזרות. דוגמה: \begin{example}$\frac{1}{n^2}=o(\frac{1}{n}),n\to\infty $\end{example}

4. \item $ a_n\sim b_n, n\to \infty$ אם ורק אם $\lim_{n\to \infty} \frac{a_n}{b_n} = 1 $\end{enumerate}