Asymptotic notation and growth rates of functions

Prove that:

Prove that:

Find the following limit: $\lim \limits_{x\to 0}\dfrac {1}{x^{100}}e^{-\frac{1}{x^{2}}}$.

Find the following limit: $\lim \limits_{x\to +0}x\ln x$.

Let $o(f(x))$ denote, as $x\to a$, an arbitrary infinite function of lower order than the function $f(x)$, and let $O(f(x))$ denote, as $x\to a$, an arbitrary infinite function of the same order (in the generalized sense) as the function $f(x)$, where $f(x)>0$.

Prove:

Let $x\to +0$ and $n>0$. Prove

Let $x\to +\infty$ and $n>0$. Prove

Let $x\to +0$. Prove the following equalities:

Let $x\to +\infty$. Prove the following equalities:

Prove that when $x$ is sufficiently large, the following inequalities hold:

Let $x\to +\infty$ and $f_{n}(x)=x^{n}$ ($n=1,2,\ldots$). Prove that:

Let $x\to +\infty$ and $f_{n}(x)=\sqrt[n]{x}$ ($n=1,2,\ldots$). Prove that:

Prove that for any sequence of functions

one can exhibit a function $f(x)$ that, as $x\to +\infty$, increases faster than each of the functions $f_{n}(x)$ ($n=1,2,\ldots$).

$x^{2}+10x+100<0.001x^{3}$;

Show that $2^{\ln n}=o(n)$ and $2^{\log (2 n)}=O(n)$.

Show that $(\log n)^{10} \prec n^{10} \prec 2^{(\log n)^{10}}$.

Compare the following three functions using the $\prec$ notation:

Compare $2^{\log { }^{*} n}$ with $n$ using the $\prec$ notation.

Suppose that $f(n) \prec g(n)$. Is it true that for any increasing function $h(n)$ with $\lim_{n \rightarrow \infty } h(n)=\infty , h(f(n)) \prec h(g(n))$? Present a proof or a counterexample.

Prove that $\log^{(k+1)} \prec \log^{(k)} n$ for any $k \geq 0$.

Denote $\log^{* *} n=\min \left\{ k \mid \left(\log^{*}\right)^{(k)} n \leq 1, k \geq 1\right\}$. Compare $\log^{* *} n$ with $\log^{*} n$.

Recall the Ackermann function $A$ defined in Exercise 8 of Section 4.8.

Suppose we are given three pegs and $n$ disks, with all $n$ disks having different size. Initially, the $n$ disks are stacked in decreasing size, from bottom to top, in the first peg (see Figure 6.1). The Tower of Hanoi problem is to transfer the entire tower of $n$ disks from the first peg to the second peg, moving one disk at a time and never putting a larger disk on top of a smaller disk. What is the fastest solution to this problem? Is the fastest solution feasible for size $n=64$ (the size of the original Tower of Hanoi problem)?

Figure 6.1: The Tower of Hanoi problem.

Show that the function $2^{\sqrt{\log n}}$ grows slower than every function in the polynomial sequence, but faster than every function in the poly-log sequence.

Suppose $f(n) \prec g(n)$. Show that there exists a function $h(n)$ such that $f(n) \prec h(n) \prec g(n)$.

Show that $\log^{*} n \prec \log^{(m)} n$ for any constant integer $m \geq 1$.