Asymptotic Notation¶
Question
Which of these symbols:
Apply the following equations? List all that apply.
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,
2
Prove that \(f^2 \backsim g^2\).
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,
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,
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,
Since both k and j are finite, then so is kj.
More Asymptotic Notation¶
1
Show that
where \(a, b\) are positive constants and \(\backsim\) denotes aymptotic equality. Hint: \(an = a2^{\log_2 n}\).
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
By stirling’s formula we know,
where \(\varepsilon (n)\) equates to zero at the limit
So we can continue evaluating \(n!\)
By definition \(\sqrt [n] {n!} = \Theta (n)\) if
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.