Notes - DAA HT23, Asymptotic notation

Can you define the set $O(g(n))$?

\[\\{ f: \mathbb{N} \to \mathbb{R}^+ : \exists k \in \mathbb{N} \text{ } \exists c > 0 \text{ s.t. } \forall n > k, \text{ } f(n) \le cg(n) \\}\]

What do we really mean when we write $f(n) = O(g(n))$?

\[f(n) \in O(g(n))\]

What does the notation

\[f_1(n) = f_2(n) + O(g(n))\]

mean?

\[f_1(n) = f_2(n) + h(n)\]

where $h(n)$ is some function in $O(g(n))$.

Whato does the notation

\[f(n) = \Omega(g(n))\]

mean?

\[g(n) = O(f(n))\]

What does the notation $f(n) = \Theta(g(n))$ mean?

\[f(n) = O(g(n)) \text{ and } f(n) = \Omega(g(n))\]

When, in terms of limits, is $f(x) = O(g(x))$ true?

\[\lim_{n \to \infty} \left|\frac{f(x)}{g(x)}\right| = L, 0 \le L< \infty\]

When, in terms of limits, is $f(x) = \Omega(g(x))$ true?

\[\lim_{n \to \infty} \left| \frac{f(x)}{g(x)} \right| = L, 0 < L \le \infty\]

When, in terms of limits, is $f(x) = \Theta(g(x))$ true?

\[\lim_{n \to \infty} \left| \frac{f(x)}{g(x)} \right| = L, 0 < L < \infty\]

Say

\[\lim_{n \to \infty} \left| \frac{f(x)}{g(x)} \right| = L\]

When are the following true?