1 - Asymptotic Analysis

Recalling the definition Asymtotic Notation, we have the following problems: In the analysis of algorithms, we are mostly concerned with function of the type $f$ from $N$ to $R^{+}$ , where $f (n)$ depicts the count of basic operations in the Word-RAM model, for an input size of $n$ . $f (n)$ is allowed to be real, just for relaxation.
Note that $f$ is increasing in $n$ , it would be kind of weird if a larger input required less computations in our model.

Any polynomial/sub-polynomial beats any logarithmic power

For any $a, b \in R^{+}$ , $\log (n)^{a} = O (n^{b})$ . But $n^{b} \neq O (\log (n)^{a})$ .

$* p r o o f * :$
First, we will show that there is an absolute constant $C > 0$ such that $\log (n)^{a} \leq C n^{b}$ . Notice the following series of equations, (exploiting the fact that $\log$ is increasing)

a \log (\log n) \leq \log C + b \log n

\log C \geq a \log (\log n) - b \log (n)

Now set $g (x) = a \log (\log x) - b \log x$ . for $x \geq 1$ and $x \in R$ . We claim that $g (x)$ has an absolute maximum. $$g'(x) = \frac{1}{x}\left( \frac{a}{\log x} - b \right)$$
Notice that $g^{'} (x) = 0$ at $x = e^{a / b}$ , and for $x < e^{a / b}$ , $g^{'} (x) > 0$ , for $x > e^{a / b}$ $g^{'} (x) < 0$ . Hence $g (e^{a / b})$ is the absolute maximum of $g$ . It's sufficient to set $\log C \geq g (e^{a / b})$ .

Now, we will show that there is no absolute constant $D > 0$ such that $n^{b} \leq D (\log n)^{a}$ . Again $$ b \log n \le \log D + a \log(\log n)$$

\log D \geq b \log n - a \log (\log n) = - g (n)

notice that $- g (x)$ is increasing, and unbounded for real $x$ . We will leave it to the reader to prove this.
$◻$

Informal

We will not be doing any additional problems for asymptotic analysis.

Asymptotics Exercises

Find a simple, tight asymptotic bound for $(\binom{n}{6006})$ .

Solution: Definition yields $n (n - 1) \dots (n - 6005)$ in the numerator (a degree 6006 polynomial) and $6006!$ in the denominator (constant with respect to $n$ ). So $(\binom{n}{6006}) = Θ (n^{6006})$ .

Find a simple, tight asymptotic bound for $\log_{6006} ({(\log (n^{\sqrt{n}}))}^{2})$ .

Solution: Recall exponent and logarithm rules: $\log a b = \log a + \log b, \log (a^{b}) = b \log a$ , and $\log_{a} b = \log b / \log a$ .

\begin{aligned} \log_{6006} ({(\log (n^{\sqrt{n}}))}^{2}) & = \frac{2}{\log 6006} \log (\sqrt{n} \log n) \\ = Θ (\log n^{1 / 2} + \log \log n) = Θ (\log n) \end{aligned}

Show that $2^{n + 1} \in Θ (2^{n})$ , but that $2^{2^{n + 1}} \notin O (2^{2^{n}})$ .

Solution: In the first case, $2^{n + 1} = 2 \cdot 2^{n}$ , which is a constant factor larger than $2^{n}$ . In the second case, $2^{2^{n + 1}} = {(2^{2^{n}})}^{2}$ , which is definitely more than a constant factor larger than $2^{2^{n}}$ .

Show that $(\log n)^{a} = O (n^{b})$ for all positive constants $a$ and $b$ .

Solution: It's enough to show $n^{b} / (\log n)^{a}$ limits to $\infty$ as $n \to \infty$ , and this is equivalent to arguing that the log of this expression approaches $\infty$ :

lim_{n \to \infty} \log (\frac{n^{b}}{(\log n)^{a}}) = lim_{n \to \infty} (b \log n - a \log \log n) = lim_{x \to \infty} (b x - a \log x) = \infty,

as desired.
Note: for the same reasons, $n^{a} = O (c^{n})$ for any $c > 1$ .

Show that $(\log n)^{\log n} = Ω (n)$ .

Solution: Note that $m^{m} = Ω (2^{m})$ , so setting $n = 2^{m}$ completes the proof.

Show that $(6 n)! \notin Θ (n!)$ , but that $\log ((6 n)!) \in Θ (\log (n!))$ .
Solution: We invoke Sterling's approximation,

n! = \sqrt{2 π n} {(\frac{n}{e})}^{n} (1 + Θ (\frac{1}{n}))

Substituting in $6 n$ gives an expression that is at least $6^{6 n}$ larger than the original. But taking the logarithm of Sterling's gives $\log (n!) = Θ (n \log n)$ , and substituting in $6 n$ yields only constant additional factors.

Asymptotic Analysis using limits

we can loosen our definition of big- $O$ notation, by allowing $f = O (g)$ if we have $f (n) \leq C g (n)$ for each $n > N_{0}$ for some $N_{0} \in N$ .
Using this definition, we have the following proposition:

Finite limiting ratio and Asymptotics

Let $f, g : N \to R^{+}$ if $lim_{n \to \infty} \frac{f (n)}{g (n)} = C > 0$ , then $f = O (g)$ .

$* p r o o f * :$ Notice that for each $ϵ > 0$ there exists $N (ϵ)$ such that when $n > N (ϵ)$ : $$\Bigg|\frac{f(n)}{g(n)} - C \Bigg | < \epsilon$$
Rearranging, and choosing any small epsilon that we like :) we have $f (n) < (C + ϵ) g (n)$ for each $n \geq N (ϵ)$ . Hence $f = O (g)$ .

Informal

Notice that $f = O (g)$ doesn't say too much about the limits, and is well defined when neither $f$ nor $g$ converge, however, since $\frac{f (n)}{g (n)} \leq C$ for each $n \in N$ , it is indeed true that the limit superior of $f / g$ is at most $C$ . (just look at all convergent subsequences of $f / g$ , they are all bounded above by $C$ , so the one with the largest limit is also bounded above by $C$ ).

$◻$