3. Characterizing Running Times

Exercises

3.1-1

Available in the latest revision of the IM.

3.1-2

Available in the latest revision of the IM.

3.1-3

Available in the latest revision of the IM.

3.2-1 🌟

Proves that $\max\{f(n), g(n)\}=\Theta(f(n)+g(n))$.

Available in the latest revision of the IM.

3.2-2

Available in the latest revision of the IM.

3.2-3

Available in the latest revision of the IM.

3.2-4

Available in the latest revision of the IM.

3.2-5

Available in the latest revision of the IM.

3.2-6

Available in the latest revision of the IM.

3.2-7 🌟

Defines asymptotic tight bounds for a function $f(n,m)$ with two independent arguments.

Available in the latest revision of the IM.

3.3-1 🌟

Proves some properties about monotonically increasing functions $f(n)$ and $g(n)$.

Let $m \le n$. This implies that $f(m) \le f(n)$ and $g(m) \le g(n)$, since they are monotonically increasing functions.

If we add up these inequalities, then we get $f(m)+g(m)\le f(n)+g(n)$, thus proving that $f(n)+g(n)$ is monotonically increasing. If we multiply these inequalities, provided that both $f$ and $g$ are nonnegative, then we get $f(m) \cdot g(m)\le f(n) \cdot g(n)$, thus proving that $f(n) \cdot g(n)$ is monotonically increasing.

By definition $f(g(m)) \le f(g(n))$, so the composition $f(g(n))$ is also monotonically increasing.

3.3-2 🌟

Proves that $\lfloor \alpha n\rfloor+\lceil(1-\alpha)n\rceil=n$ for any integer $n$ and real $0 \le \alpha \le 1$.

Available in the latest revision of the IM.

3.3-3 🌟

Proves that $(n+o(n))^k=\Theta(n^k)$ for any real constant $k$, thus $\lceil n\rceil^k=\Theta(n^k)$ and $\lfloor n\rfloor^k=\Theta(n^k)$.

$f(n)=o(n)$ implies that $0 \le f(n) < cn$ for all $c >0$ and $n \ge n_0$. For $n \ge n_0$ we have$n \le n + f(n) < (1+c)n$, thus $n+o(n)=\Theta(n)$, since we can choose any constant greater than 1 for the upper bound. Analogously, we can prove that $n-o(n)=\Theta(n)$ by simply reversing inequalities $n \ge n-f(n)>(1-c)n$ and choosing any positive constant less than 1 for the lower bound.

Consequently,

$$\underbrace{(n+o(n))^k}_{f(n)}=(\Theta(n))^k \implies c_1^kn^k \le f(n) \le c_2^kn^k \implies f(n)=\Theta(n^k),$$

for any real constant $k$. As a side note, if $k <0$, then the inequalities of $\Theta$ are reverse of those when $k>0$.

By definition, $n \le \lceil n \rceil < n + 1$. Let $f(n) = \lceil n \rceil - n$. Since $0 \le f(n) < 1 \implies f(n)=o(n)$ (any constant is asymptotically smaller than $n$), this gives $\lceil n\rceil=n+o(n)$, thus $\lceil n\rceil^k=\Theta(n^k)$. In virtually the same way, we can show that $\lfloor n\rfloor=n-o(n)$, so $\lfloor n\rfloor^k=\Theta(n^k)$.

3.3-4

a.

$$\begin{align*} \large a^{\large\log_b c} &= \large a^{\cfrac {\log_a c}{\log_a b}} && \text{(by equation (3.19))} \\ &= \large c^{\cfrac {1}{\log_a b}} && \text{(by equation (3.17))} \\ &= \large c^{\large\log_b a}. \end{align*}$$

b.

$$\frac {n!}{n^n}=\frac{1}{n} \cdot \frac{2}{n} \dots \frac{n}{n} \implies \lim_{n \to \infin} \frac{n!}{n^n}=0.$$

Observe that the largest term on the right side is 1, whilst the initial terms tend to zero as n increases. Therefore, $n!=o(n^n)$.

$$\frac {n!}{2^n}=\frac{1}{2} \cdot \frac{2}{2} \dots \frac{n}{2} \implies \lim_{n \to \infin} \frac{n!}{2^n}=\infin.$$

Here, we have an opposite situation, thus $n!=\omega(2^n)$.

A weak upper bound on the factorial function is $n! \le n^n$, so $\lg n! \le n\lg n=O(n\lg n)$.

$$\begin{align*} \lg n! &= \lg {(\sqrt{2\pi n}\,(n/e)^n e^{\alpha_n})} && \text{(by equation (3.29))} \\ &> \lg {(n/e)^n} \\ &> \lg {(\sqrt n)^n} && \text{(} e < \sqrt n \text{ when } n \ge 9 \text{)} \\ &= \frac {n \lg n}{2} \\ &\therefore \lg n! = \Omega(n \lg n). \end{align*}$$

Theorem 3.1 implies that $\lg n!=\Theta(n\lg n)$.

c.

Let $f(n)=\Theta(n)$. By definition $c_1n \le f(n) \le c_2n$ for some positive constants and $n \ge n_0$.

$$\begin{align*} \lg f(n) &\ge \lg c_1n \\ &=\lg c_1 + \lg n \\ &\ge \lg \frac{1}{\sqrt n} + \lg n && \text{(when } n \ge 1/c_1^2 \text{)} \\ &= \lg \sqrt n \\ &= \frac {\lg n}{2} \\ &\therefore \lg f(n) = \Omega(\lg n). \\ \hline \\ \lg f(n) &\le \lg c_2n \\ &=\lg c_2 + \lg n \\ &\le 2\lg n && \text{(when } n \ge c_2 \text{)} \\ &\therefore \lg f(n) = O(\lg n). \end{align*}$$

Theorem 3.1 implies that $\lg f(n)=\lg \Theta(n)=\Theta(\lg n)$ for all $n \ge \max\{n_0,1/c_1^2,c_2\}$.

★ 3.3-5 🌟

Proves that a function $f(n)$ is polynomially bounded if and only if $\lg f(n)= O(\lg n)$.

Available in the latest revision of the IM.

★ 3.3-6

Available in the latest revision of the IM.

3.3-7

Available in the latest revision of the IM.

3.3-8

Available in the latest revision of the IM.

3.3-9 🌟

Illustrates the symmetry property of the $\Theta$ notation by showing that $k\lg k=\Theta(n)$ implies $k=\Theta(n/\lg n)$.

Available in the latest revision of the IM.

Problems

3-1 Asymptotic behavior of polynomials

In all subproblems, we rely on the fact (stated in the book on page 65) that for an asymptotically positive polynomial $p(n)$ of degree $d$, we have $p(n)=\Theta(n^d)$. Consequently, for some positive constants it holds that $0 < c_1n^d \le p(n) \le c_2n^d$ for all $n \ge n_0$.

a.

$n^k \ge n^d$ for all $n \ge 1$, so $0 < p(n) \le c_2n^d \le c_2n^k$ for all $n \ge n_0$. Thus, $p(n)=O(n^k)$.

b.

$n^k \le n^d$ for all $n \ge 1$, so $0 < c_1n^k \le c_1n^d \le p(n)$ for all $n \ge n_0$. Thus, $p(n)=\Omega(n^k)$.

c.

$k=d$ means that $k \ge d \land k \le d$, so parts (a) and (b) apply. Theorem 3.1 implies that $p(n)=\Theta(n^k)$.

d.

We fix a positive constant $c$ and show that for sufficiently large $n$ we have $c_2n^d < cn^k$. We can rewrite this inequality as $c_2/c < n^{k-d}$. Apparently, it holds for all $n > (c_2/c)^{1/(k-d)}$. Choosing $n$ to be the maximum of this value and $n_0$ ensures that $0 < p(n)\le c_2n^d<cn^k$. As the choice of $c$ was arbitrary, the derivation applies to all positive constants, hence $p(n)=o(n^k)$.

e.

We fix a positive constant $c$ and show that for sufficiently large $n$ we have $c_1n^d > cn^k$. We can rewrite this inequality as $c/c_1 < n^{d-k}$. Apparently, it holds for all $n > (c/c_1)^{1/(d-k)}$. Choosing $n$ to be the maximum of this value and $n_0$ ensures that $0 < cn^k < c_1n^d \le p(n)$. As the choice of $c$ was arbitrary, the derivation applies to all positive constants, hence $p(n)=\omega(n^k)$.

3-2 Relative asymptotic growths

Available in the latest revision of the IM.

3-3 Ordering by asymptotic growth rates

Available in the latest revision of the IM.

3-4 Asymptotic notation properties

Available in the latest revision of the IM.

3-5 Manipulating asymptotic notation

Assume that all constants introduced in the subproblems are positive.

a.

Let $g(n)=\Theta(f(n))$, thus $0 \le c_1f(n) \le g(n) \le c_2f(n)$ for all $n \ge n_g$. Let $h(n)=\Theta(g(n))$, so $0 \le d_1g(n) \le h(n) \le d_2g(n)$ for all $n \ge n_h$. Substituting $g(n)$ with $f(n)$ we get $0 \le d_1c_1f(n) \le h(n) \le d_2c_2f(n)$ for all $n \ge \max\{n_g,n_h\}$. Therefore, $h(n)=\Theta(f(n))$, which concludes the proof.

b.

Let $g(n)=\Theta(f(n))$, thus $0 \le c_1f(n) \le g(n) \le c_2f(n)$ for all $n \ge n_g$. Let $h(n)=O(f(n))$, so $0 \le h(n) \le df(n)$ for all $n \ge n_h$. By combining these inequalities we get for all $n \ge \max\{n_g,n_h\}$

$$0 \le c_1f(n) \le g(n)+h(n) \le (c_2+d)f(n).$$

Therefore, $g(n)+h(n)=\Theta(f(n))$, which concludes the proof.

c.

Let $h(n)=\Theta(f(n))$, thus $0 \le c_1f(n) \le h(n) \le c_2f(n)$ for all $n \ge n_h$. Let $q(n)=\Theta(g(n))$, so $0 \le d_1g(n) \le q(n) \le d_2g(n)$ for all $n \ge n_q$. Adding together these inequalities we get for all $n \ge \max\{n_h,n_q\}$

$$0 \le \min\{c_1,d_1\}(f(n) +g(n))\le h(n) +q(n)\le \max\{c_2,d_2\}(f(n) +g(n)).$$

Therefore, $h(n)+q(n)=\Theta(f(n)+g(n))$, which concludes the proof.

d.

Let $h(n)=\Theta(f(n))$, thus $0 \le c_1f(n) \le h(n) \le c_2f(n)$ for all $n \ge n_h$. Let $q(n)=\Theta(g(n))$, so $0 \le d_1g(n) \le q(n) \le d_2g(n)$ for all $n \ge n_q$. Multiplying together these inequalities we get for all $n \ge \max\{n_h,n_q\}$

$$0 \le c_1d_1(f(n) \cdot g(n)) \le h(n) \cdot q(n) \le c_2d_2(f(n) \cdot g(n)).$$

Therefore, $h(n) \cdot q(n)=\Theta(f(n) \cdot g(n))$, which concludes the proof.

e.

$$\begin{align*} (a_1n)^{k_1} \lg^{k_2} (a_2n) &= a_1^{k_1}n^{k_1} (\lg n + \lg a_2)^{k_2} \\ &= \Theta(a_1^{k_1}n^{k_1}) (\lg n + o(\lg n))^{k_2} && \text{(by reflexivity)} \\ &= \Theta(n^{k_1}) \cdot \Theta(\lg n)^{k_2} && \text{(by Problem 3-4 part (h))} \\ &= \Theta(n^{k_1}) \cdot \Theta(\lg^{k_2} n) && \text{(by repeatedly applying part (d))} \\ &= \Theta(n^{k_1}\lg^{k_2} n) && \text{(by part (d))}. \end{align*}$$

3-6 Variations on O and Ω

a.

If $f(n)=O(g(n))$ or $f(n)=\Omega(g(n))$ (or both), then we are done. Observe that $f(n)=\Omega(g(n))$ implies $f(n)=\overset{\infty}{\Omega}(g(n)).$

Suppose that $g(n)$ cannot bound $f(n)$. There must be infinitely many points where $f(n) > cg(n)$, otherwise we could find a positive threshold $n_0$ such that $f(n) \le cg(n)$ for all $n \ge n_0$. In other words, for any $n_0$ there is some $m>n_0$ where $f(m) >cg(m)$. Consequently, $f(n)=\overset{\infty}{\Omega}(g(n)).$

b.

See Problem 3-2 row (c).

c.

As shown in part (a), one advantage of using omega infinity over standard omega is that all asymptotically nonnegative functions become asymptotically comparable. On the other hand, omega infinity cannot tell whether one function is "larger" than the other. Oscillations are permitted. Furthermore, we don't know anything about how those infinitely many points are distributed. With omega notation it is clear that the condition holds for all $n \ge n_0$. Finally, omega infinity is unknown to most software engineers.

d.

$f(n)=\Omega(g(n))$ implies that $f(n)$ is an asymptotically nonnegative function, hence $f(n)=|f(n)|$. Consequently, $f(n)=O'(g(n))$ is equivalent to $f(n)=O(g(n))$, so Theorem 3.1 remains valid.

e.

$$\begin{align*} \widetilde{\Omega}(g(n)) = \{f(n):\,{} & \text{there exist positive constants $c$, $k$, and $n_0$ such that} \\ & \text{$0 \le \dfrac{cg(n)}{\lg^kn} \le f(n)$ for all $n \ge n_0$}\} \\[2mm] \widetilde{\Theta}(g(n)) = \{f(n):\,{} & \text{there exist positive constants $c_1$, $c_2$, $k_1$, $k_2$, and $n_0$ such that} \\ & \text{$0 \le \dfrac{c_1g(n)}{\lg^{k_1}n} \le f(n) \le c_2g(n)\lg^{k_2}n$ for all $n \ge n_0$}\} \end{align*}$$

The proof of the corresponding analog to Theorem 3.1 is essentially the same as for the original version (see Exercise 3.2-4). The only difference is that we should use these new definitions.

3-7 Iterated functions

Available in the latest revision of the IM.