Design and Analysis of Algorithms HT23, Asymptotic Notation
Flashcards
@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 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))$.
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 \vert \frac{f(x)}{g(x)}\right \vert = L, 0 \le L< \infty\]
When, in terms of limits, is $f(x) = \Omega(g(x))$ true?
\[\lim _ {n \to \infty} \left \vert \frac{f(x)}{g(x)} \right \vert = L, 0 < L \le \infty\]
When, in terms of limits, is $f(x) = \Theta(g(x))$ true?
\[\lim _ {n \to \infty} \left \vert \frac{f(x)}{g(x)} \right \vert = L, 0 < L < \infty\]
Say
\[\lim _ {n \to \infty} \left \vert \frac{f(x)}{g(x)} \right \vert = L\]
When are the following true?
- $f(x) = O(g(x))$
- $f(x) = \Omega(g(x))$
- $f(x) = \Theta(g(x))$
- $f(x) = O(g(x)), 0 \le L < \infty$
- $f(x) = \Omega(g(x)), 0 < L \le \infty$
- $f(x) = \Theta(g(x)), 0 < L < \infty$