James Madison University, Fall 2024

Big-O Exercises

Definitions of Big-O, Big- $Ω$ , Big- $Θ$

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) for all n > n_{0}$
Big $Ω$	For $T (n)$ a non-negative function, $T (n)$ $\in$ $Ω (f (n))$ if and only if there exist positive constants $c$ and $n_{0}$ such that $T (n) \geq c f (n) for all n > n_{0}$
Big $Θ$	$f (n) \in Θ (g (n))$ iff $f (n) \in O (g (n)) and f (n) \in Ω (g (n))$

Limit Definitions

$\begin{array}{r} 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 Θ (g (n)) \\ \in (0, \infty], & f (n) \in Ω (g (n)) \end{cases} \end{array}$

Exercise 1

Use the non-limit definition of big-O to demonstrate that

$12 n^{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) = 10 n^{2} + 3 n$ and $g (n) = n^{4}$ by finding $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 $lim_{n \to \infty} \frac{f (n)}{g (n)}$ .

Some potentially helpful reminders:

$\log_{b} a = \frac{\log_{d} a}{\log_{d} b}$ , $\frac{d}{d x} \ln x = \frac{1}{x}$ , $\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) = 10 n^{3}$ ?