Asymptotics and Big-Oh

Videos (0 mins)

No videos for today!

Reading (50 mins)

This is a more challenging reading than usual. Please take your time. You’ll need it for the warmup problems!

Discrete Mathematics and Its Applications by Kenneth Rosen, Section 3.2, up to and including Example 7 (pages 204-211)

Warmup (50 mins)

Problem 1

Write a careful proof that \(\frac{n^2 - 1}{2n+2} \in O(n)\). You may assume that \(n \in \mathbb{N}\). Your proof should include a choice of the witnesses \(C\) and \(k\) 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))\)).

(Optional Challenge) Problem 4

You don’t need to complete this problem in order to earn credit for completing 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))\) (Definition 1 in Rosen), 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))\).