Asymptotic Notation

Question

Which of these symbols:

\[(\Theta, O, \Omega, o, \omega)\]

Apply the following equations? List all that apply.

\[ \begin{align}\begin{aligned}\begin{aligned}\\2n + \log n &= \boxed{ \Theta, O, \Omega} (n)\\Proof: \lim_{n \rightarrow \infty} {2n + \log n \over n} &= {2n \over n} + {\log n \over n} = 2 + 0 = 2 \cr\\\log n &= \boxed{ O, o } (n)\\Proof: \lim_{n \rightarrow \infty} {\log n \over n} &= 0 \cr\\\sqrt{n} &= \boxed{ \Omega, \omega } (\log^300 n)\\Proof: \lim_{n \rightarrow \infty} {\sqrt{n} \over \log^{300} n} &= \infty \cr\\n2^n &= \boxed{ \Omega, \omega } (n)\\Proof: \lim_{n \rightarrow \infty} {n2^n \over n} &= \infty \cr\\n^7 &= \boxed{ O, o } (1.01^n)\\Proof: \lim_{n \rightarrow \infty} {n^7 \over 1.01^n} &= 0 \cr\\\end{aligned}\end{aligned}\end{align} \]

Asymptotic Equivalence

Intro

Suppose \(f, g: \Bbb Z+ \rightarrow \Bbb Z+\) and \(f \backsim g\).

1

Prove that \(2f \backsim 2g\)

\(f \backsim g\) implies \(\lim_{x \rightarrow \infty} {f(x) \over g(x)} = 1\). If we compare f and g we get,

\[{ \bcancel{2}f(x) \over \bcancel{2}g(x)} = {f(x) \over g(x)} = 1\]

2

Prove that \(f^2 \backsim g^2\).

\[\lim_{x \rightarrow \infty} {f(x)^2 \over g(x)^2} = {f(x) \over g(x)} \cdot {f(x) \over g(x)} = 1 \cdot 1 = 1\]

3

Give examples of f and g such that \(2^f \cancel{\backsim} 2^g\).

4

Show that \(\backsim\) is an equivalence relation

It is reflexive, because \(\lim_{x \rightarrow \infty} {f(x) \over f(x)} = 1\), as long as \(f(x) \ne 0\).

It is transitive, because if \(\lim_{x \rightarrow \infty} {f(x) \over g(x)} = 1\) and \(\lim_{x \rightarrow \infty} {g(x) \over h(x)} = 1\), then we can multiply the limits to get,

\[\lim_{x \rightarrow \infty} {f(x) \over h(x)} = \lim_{x \rightarrow \infty} {f(x) \over g(x)} \cdot {g(x) \over h(x)} = 1 \cdot 1 = 1\]

It is symmetric, because if \(\lim_{x \rightarrow \infty} {f(x) \over g(x)} = 1\), then the following is also true \(\lim_{x \rightarrow \infty} {g(x) \over f(x)} = 1\) by limit laws of quotients, as long as \(f(x) \ne 0\) and \(g(x) \ne 0\).

Those are the properties required of equivalence relations, so \(\backsim\) is an equivalence relation.

5

Show that \(\Theta\) is an equivalence relation

In order for the following to be true,

\[0 < \lim_{x \rightarrow \infty} {f(x) \over g(x)} < \infty\]

Then we know \(f(x)\) can’t be zero, because \(\forall x \in \Bbb R. {0 \over x}= 0\). Since we know it’s not zero, then it must be reflexive because \(\lim_{x \rightarrow \infty} {f(x) \over f(x)} = 1\), which is between zero and infinity.

It is symmetric because if \(f = \Theta(g)\) then \(\lim_{x \rightarrow \infty} {f(x) \over g(x)} = k\) where k is some constant between zero and infinity. \(\lim_{x \rightarrow \infty} {f(x) \over g(x)} = {1 \over k}\) then proves the symmetry.

It is transitive, because if \(f = \Theta(g)\) and \(g = \Theta(h)\) then \(\lim_{x \rightarrow \infty} {f(x) \over g(x)} = k\) where \(0 < k < \infty\) and \(\lim_{x \rightarrow \infty} {g(x) \over h(x)} = j\) where \(0 < j < \infty\). So by multiplying the limits we get,

\[\lim_{x \rightarrow \infty} {f(x) \over g(x)} \cdot \lim_{x \rightarrow \infty} {g(x) \over h(x)} = k \cdot j\]

Since both k and j are finite, then so is kj.

More Asymptotic Notation

1

Show that

\[(an)^{{b \over n}} \backsim 1\]

where \(a, b\) are positive constants and \(\backsim\) denotes aymptotic equality. Hint: \(an = a2^{\log_2 n}\).

\[ \begin{align}\begin{aligned}\begin{aligned}\\(an)^{{b \over n}} &= (a^b)^{1 \over n} \cdot 2^{{b \log_2 n \over n}}\\&= (a^b)^0 \cdot 2^0\\&= 1 \cdot 1\\&= 1\\\end{aligned}\end{aligned}\end{align} \]

2

You may assume that if \(f(n) \ge 1\) and \(g(n) \ge 1\) for all n, then :math`f backsim g Rightarrow f^{1 over n} backsim g^{1 over n}`. Show that

\[\sqrt [n] {n!} = \Theta(n)\]

By stirling’s formula we know,

\[\lim_{n \rightarrow \infty} \sqrt [n] {n!} \backsim \sqrt [n] {({n \over e})^n \cdot \sqrt {2 \pi n} \cdot e^{\varepsilon(n)}}\]

where \(\varepsilon (n)\) equates to zero at the limit

\[ \begin{align}\begin{aligned}\lim_{n \rightarrow \infty} {1 \over 12n+1} \le \varepsilon (n) \le {1 \over 12n}\\\lim_{n \rightarrow \infty} 0 \le \varepsilon (n) \le {1 \over 12n}\\\varepsilon (n) \backsim 0\end{aligned}\end{align} \]

So we can continue evaluating \(n!\)

\[ \begin{align}\begin{aligned}\backsim \sqrt [n] { ({n \over e})^n \cdot \sqrt {2 \pi n} \cdot e^0 }\\\backsim \left ( ({n \over e})^n \cdot (2 \pi n)^{1 \over 2} \cdot 1 \right )^{1 \over n}\\\backsim \left ( ({n \over e})^{\cancel{n}} \right )^\cancel{{1 \over n}} \cdot \left ( (2 \pi n)^{1 \over 2} \right )^{1 \over n}\\\backsim {n \over e} \cdot \left ( (2 \pi n)^{1 \over 2} \right )^0\\\backsim {n \over e} \cdot 1\\\backsim {n \over e}\\\backsim \infty\end{aligned}\end{align} \]

By definition \(\sqrt [n] {n!} = \Theta (n)\) if

\[\lim_{n \rightarrow \infty} 0 < | {\sqrt [n] {n!} \over n}| < \infty\]

As shown above \(\sqrt [n] {n!}\) trends towards infinity, and since \({\infty \over \infty} = 1\) and 1 is between zero and infinity so \(\Theta (n)\) holds.