Skip to main content

Section A.1 Exercises

  1. Determine whether each of the following is true or false. The answers are in footnote
     1 
    (a) T, (b) T, (c) F, (d) T, (e) F, (f) T, (g) F, (h) T, (i) T, (j) F, (k) T, (l) T, (m) T, (n) T, (o) T, (p) T, (q) F, (r) T, (s) F, (t) T, (u) T, (v) F, (w) F.
    1. \(x^7 +x^5 = o(x^9)\text{.}\)
    2. \(x^{100} = O(2^x)\text{.}\)
    3. \(x^9 = O(x^{10}\sin(x))\text{.}\)
    4. \(x^2 -9x = \Theta(x^2)\text{.}\)
    5. \(e^{x^2-9x} = \Theta(e^{x^2})\text{.}\)
    6. \(n^8 = 2^{O(\log(n))}\text{.}\)
    7. \(3^{\sqrt{\log(n)}} = \Omega(n)\text{.}\)
    8. \(7^{\log\log(n)} = \log(n)^{O(1)}\text{.}\)
    9. \(|E(K_n)|= (1+o(1))(n^2/2)\text{.}\)
    10. \(\binom{n}{5}\sim n^5\text{.}\)
    11. \(e^{2\pi}=\Omega(1)\text{.}\)
    12. \(e^{-x} +x = \Theta(1)\) as \(x\to 0\text{.}\)
    13. \(e^{-x} +x = 1+o(1)\) as \(x\to 0\text{.}\)
    14. \(\frac{7n^3 - 4n^2 + \pi n}{42n^2 - 22n+77} = \Theta(n)\text{.}\)
    15. \(n!=O(n^n)\text{.}\)
    16. If \(v\) is a vertex of a graph \(G\) with \(n\) vertices, then the number of triangles in \(G\) containing \(v\) is \(O(n^2)\text{.}\)
    17. For every \(n\geq1\text{,}\) there exists a graph \(G\) with \(n\) vertices and \(\Omega(n^3\log\log(n))\) triangles.
    18. The number of subsets of \([n]\) is \(2^{O(n)}\text{.}\)
    19. The number of subsets of \([n]\) is \(2^{o(n)}\text{.}\)
    20. The number of subsets of \([n]\) is \(\Omega\left(2^n\right)\text{.}\)
    21. The number of subsets of \([n]\) is \((1-o(1))2^n\text{.}\)
    22. The number of subsets of \([n]\) is \(\Theta(n)\text{.}\)
    23. If \(f(n)=\Theta(n^2)\text{,}\) then \(\lim_{n\to\infty}\frac{f(n)}{n^2}\) exists.
  2. Find three functions \(f,g,h:\mathbb{N}\to\mathbb{N}\) such that all four of the following conditions hold:
    • \(f(n)>h(n)\) for all \(n\geq1\text{,}\)
    • \(g(n)>h(n)\) for all \(n\geq 1\text{,}\)
    • \(f\sim g\text{,}\)
    • \(f-h\nsim g-h\text{.}\)
  3. Give an example of two functions \(f,g:\mathbb{N}\to\mathbb{N}\) such that \(f=\Theta(g)\) but there does not exist \(c\in \mathbb{R}\) such that \(f\sim c\cdot g\text{.}\)
  4. Let \(\ell\leq k\) be a fixed positive integers and let \(n\) be an integer which is tending to infinity. Explain why the following is true:
    \begin{equation*} \frac{\binom{37\ell^k n + 92}{k}}{\binom{n-2^\ell}{k-\ell}}=\Theta(n^\ell)\text{.} \end{equation*}
  5. Note that this question is not really about asymptotic notation, but it does test your understanding of the growth rate of functions. Let \(r:\mathbb{N}\to\mathbb{N}\) and \(m:\mathbb{N}\to\mathbb{N}\text{.}\)
    1. Suppose that
      \begin{equation*} \frac{n}{\exp({\sqrt{\log(n)}})}\leq r(n),m(n)\leq n \end{equation*}
      for all \(n\in \mathbb{N}\text{.}\) Prove that there exists \(\alpha>0\) and an infinite subset \(N\) of \(\mathbb{N}\) such that
      \begin{equation*} \frac{r(n)}{n} \geq \alpha\cdot \frac{r(m(n))}{m(n)} \end{equation*}
      for all \(n\in N\text{.}\) How big can you make \(\alpha\text{?}\)
    2. Suppose now that
      \begin{equation*} \frac{n}{\exp({\log^{0.51}(n)})}\leq r(n),m(n)\leq n \end{equation*}
      for all \(n\in \mathbb{N}\text{.}\) Does the same conclusion as Exercise 5.a still hold?