CS 240: Algorithms and Data Structures
James Madison University, Fall 2024

Big-O Exercises

Definitions of Big-O, Big-\(\Omega\), Big-\(\Theta\)

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))\]

Limit Definitions

\[ \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} \]

Exercise 1

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.)

Exercise 2

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)}\). Your solution must show each step of the derivation. In the end, either the numerator, the denominator, or both, must be constants.

 

Exercise 3

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}}\)

Exercise 4

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\)?