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{.}\)
For every \(n\geq1\text{,}\) there exists a graph \(G\) with \(n\) vertices and \(\Omega(n^3\log\log(n))\) triangles.
The number of subsets of \([n]\) is \(2^{O(n)}\text{.}\)
The number of subsets of \([n]\) is \(2^{o(n)}\text{.}\)
The number of subsets of \([n]\) is \(\Omega\left(2^n\right)\text{.}\)
The number of subsets of \([n]\) is \((1-o(1))2^n\text{.}\)
The number of subsets of \([n]\) is \(\Theta(n)\text{.}\)
If \(f(n)=\Theta(n^2)\text{,}\) then \(\lim_{n\to\infty}\frac{f(n)}{n^2}\) exists.
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{.}\)
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{.}\)
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*}
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{.}\)
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