Asymptotics and Big-Oh Notation

Videos

Reading

Connecting Discrete Mathematics and Computer Science by David Liben Nowell: Section 6.2 (pages 5-15)

Warmup

Problem 1

Write a careful proof that \(\frac{n^2 - 1}{2n+3} \in O(n)\). You may assume that \(n \in \mathbb{N}\). Your proof should include a choice of the witnesses \(C\) and \(n_0\) and an argument for why those witnesses work.

Problem 2

Find the smallest integer \(p\) such that \(f(n) \in O(n^p)\) for each of the following choices of the function \(f\). You may assume that \(n \in \mathbb{N}\). You should explain your answers but do not need to write formal proofs. You may find it useful to remember that \(\log n \notin O(1)\) and \(\log n \leq n\) for all \(n\).

\(f(n) = 3n^2\)
\(f(n) = \log n\)
\(f(n) = n^2 \log n\)
\(f(n) = \frac{\log n}{n}\)
\(f(n) = \frac{n^3+2}{n^2 - n - 1}\)

Problem 3

Your so-called friend has a cool proof for you.

Since \(2n = O(n)\) and \(\log n = O(n)\), we know that \(2n = O(n) = \log n\). So, \(2n = \log n\) for all \(n\).

In a brief paragraph, patiently explain to your friend why this proof is incorrect. In part of your paragraph, you may wish to comment on the superiority of the notation \(f(n) \in O(g(n))\) (rather than \(f(n) = O(g(n))\)).

Problem 4 (Optional)

Note: This is an optional challenge problem. You are not required to complete it in order to earn credit for the warmup.

We can think of the statement \(f(n) \in O(g(n))\) as a relation between functions, which we could write \(fRg\). Using the definition of \(f(n) \in O(g(n))\), write a careful proof that this relation is transitive. In your proof, you should construct witnesses demonstrating that \(f(n) \in O(h(n))\) in terms of other witnesses that follow from the assumption that \(f(n) \in O(g(n))\) and \(g(n) \in O(h(n))\).