| Big-O | For \(T(n)\) a non-negative function, \(T(n)\) \(\in\) \(O(f(n))\) if and only if there exist positive constants \(c\) and \(n_0\) such that \[T(n) \leq c f(n) \text{ for all } n>n_0\] |
| Big \(\Omega\) | For \(T(n)\) a non-negative function, \(T(n)\) \(\in\) \(\Omega(f(n))\) if and only if there exist positive constants \(c\) and \(n_0\) such that \[T(n) \geq c f(n) \text{ for all } n>n_0\] |
| Big \(\Theta\) |
\(f(n) \in \Theta(g(n))\) iff \[f(n) \in O(g(n)) \text{ and } f(n) \in \Omega(g(n))\] |
\[ \begin{align} \text{if} \;\;\; \lim_{n \to \infty} \frac{f(n)}{g(n)} \begin{cases} \in [0, \infty) , \;\;\; &f(n) \in O(g(n))\\ \in (0, \infty) , \;\;\; &f(n) \in \Theta(g(n))\\ \in (0, \infty] , \;\;\; &f(n) \in \Omega(g(n))\\ \end{cases} \end{align} \]
Use the non-limit definition of big-O to demonstrate that
\[12n^2 \in O(n^2)\]
(This requires that you find constants \(c\) and \(n_0\) that satisfy the definition.)
Determine the relationship between \(f(n) = 10n^2 + 3n\) and \(g(n) = n^4\) by finding \(\displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)}\).
Determine the relationship between \(f(n) = \log_2 n\) and \(g(n) = \sqrt{n}\) by finding \(\displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)}\).
Some potentially helpful reminders:
\(\displaystyle \log_b a = \frac{\log_d a}{\log_d b}\), \(\displaystyle \qquad \frac{d}{dx}\ln x = \frac{1}{x}\), \(\displaystyle \qquad \sqrt{x} = x^{\frac{1}{2}}\)
Assume we are working with an algorithm that requires \(T(n) = n^3\) steps to complete. By what factor does the running time increase if we double the input size? How does that answer change if the running time is instead \(T(n) = 10n^3\)?