Skip to main content
Contents
Search Book
Search Results:
No results.
Read aloud Readability settings Prev Up Next \( \providecommand{\glspostdescription}{}
\renewcommand{\glspostdescription}{}
\def\cprime{\char"7E }
\def\cdprime{\char"7F }
\def\eoborotnoye{\char'013}
\def\Eoborotnoye{\char'003}
\newcommand{\beq}[1]{\begin{equation}\label{#1}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\weakstar}{weak${}^*$ }
\newcommand{\rng}{\operatorname{rng}}
\newcommand{\ex}{\operatorname{ex}}
\newcommand{\colex}{\prec_{\operatorname{colex}}}
\newcommand{\lex}{\prec_{\operatorname{lex}}}
\newcommand{\per}{\operatorname{per}}
\newcommand{\permat}{\operatorname{pm}}
\renewcommand{\hom}{\operatorname{hom}}
\newcommand{\Hom}{\operatorname{Hom}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\degree}{d}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section A.1 Exercises
Determine whether each of the following is true or false. The answers are in footnote
\(x^7 +x^5 = o(x^9)\text{.}\)
\(x^{100} = O(2^x)\text{.}\)
\(x^9 = O(x^{10}\sin(x))\text{.}\)
\(x^2 -9x = \Theta(x^2)\text{.}\)
\(e^{x^2-9x} = \Theta(e^{x^2})\text{.}\)
\(n^8 = 2^{O(\log(n))}\text{.}\)
\(3^{\sqrt{\log(n)}} = \Omega(n)\text{.}\)
\(7^{\log\log(n)} = \log(n)^{O(1)}\text{.}\)
\(|E(K_n)|= (1+o(1))(n^2/2)\text{.}\)
\(\binom{n}{5}\sim n^5\text{.}\)
\(e^{2\pi}=\Omega(1)\text{.}\)
\(e^{-x} +x = \Theta(1)\) as
\(x\to 0\text{.}\)
\(e^{-x} +x = 1+o(1)\) as
\(x\to 0\text{.}\)
\(\frac{7n^3 - 4n^2 + \pi n}{42n^2 - 22n+77} = \Theta(n)\text{.}\)
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{,}\)
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
\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{?}\)
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?
Determine whether each statement is true or false. No justification is necessary. Here
\(n\to\infty\text{.}\)
\(n^4=2^{O(\log n)}\text{.}\)
\(n^4=O(2^{\log_2 n})\text{.}\)
\(2^{\sqrt{\log n}}=n^{o(1)}\text{.}\)
\(\log(n!)=\Theta(n\log n)\text{.}\)
For every fixed
\(\varepsilon>0\text{,}\) \((\log n)^{100}=o(n^\varepsilon)\text{.}\)
