Asymptotics and Big-Oh Notation – CSCI 0200: Math Foundations of Computing

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