3.1 Asymptotic notation

3.1-1

According to the basic definition of $\Theta$-notation, if $max(f(n), g(n)) = \Theta(f(n) + g(n))$, then there exist positive constants $c_1$, $c_2$ and $n_0$ such that:

$$0 \leq c_1(f(n) + g(n)) \leq max(f(n), g(n)) \leq c_2(f(n) + g(n)),\ for \ all \ n \geq n_0$$

Because f(n) and g(n) are nongenative, so it's obvious that $max(f(n), g(n)) \leq f(n) + g(n)$, so we can let $c_2$ be 1.

And we also know that $max(f(n), g(n)) \geq f(n)$ and $max(f(n), g(n)) \geq g(n)$, so $2max(f(n), g(n)) \geq f(n) + g(n)$, thus $max(f(n), g(n)) \geq \frac{f(n) + g(n)}{2}$. So we can let $c_1$ be $\frac{1}{2}$.

Because $0 \leq \frac{f(n) + g(n)}{2} \leq max(f(n), g(n)) \leq f(n) + g(n)$ is true for all n, so we can let $n_0$ be 1.

So we've found positive constants $c_1$, $c_2$ and $n_0$, thus $max(f(n), g(n)) = \Theta(f(n) + g(n))$.

3.1-2

According to Newton's generalised binomial theorem, we have:

$$(n + a)^b = \sum_{k = 0}^{\infty} \binom{b}{k}n^{b - k}a^k = n^b + bn^{b - 1}a + \frac{b(b - 1)}{2!}n^{b - 2}a^2 + \dots$$

Since $n^b$ grows faster than others, so $(n + a)^b = \Theta(n^b)$.

3.1-3

The O-notation denotes a upper bound, so we can not say "at least".

3.1-4

$2^{n + 1} = O(2^n)$, because there exist positive constants c = 2 and $n_0 = 1$ such that $0 \leq 2^{n + 1} \leq 2 * 2^n\ for\ all\ n \geq n_0$.

$2^{2n} \neq O(2^n)$. Suppose $2^{2n} = O(2^n)$, then there exist positive constants c and $n_0$ such that $0 \leq 2^{2n} \leq c2^n\ for\ all\ n \geq n_0$, which means $0 \leq 2^n \leq c\ for\ all\ n \geq n_0$. No matter how big c is, $2^n$ will be bigger than c after a specific $n_1$, so you cannot find a $n_0$ like that.

3.1-5

If $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$, then there exist positive constants $c_1$ and $n_1$ such that $0 \leq f(n) \leq c_1g(n)\ for\ all\ n \geq n_1$, and there exist positive constants $c_2$ and $n_2$ such that $0 \leq c_2g(n) \leq f(n)\ for\ all\ n \geq n_2$. We can choose $n_0 = max(n_1, n_2)$, and combine the two inequations we have $0 \leq c_2g(n) \leq f(n) \leq c_1g(n)\ for\ all\ n \geq n_0$, which is the definition for $f(n) = \Theta(g(n))$. So we proved if $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$, then $f(n) = \Theta(g(n))$.

Now lets' suppose $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$ is not true (either one of them is wrong or both are wrong), but $f(n) = \Theta(g(n))$ is ture. And let's prove this hypothesis is not correct.

If we have $f(n) = \Theta(g(n))$, we know there exist positive constants c and $n_0$ such that $0 \leq c_1g(n) \leq f(n) \leq c_2g(n)\ for\ all\ n \geq n_0$. So we can separate it into two inequations:

$$0 \leq f(n) \leq c_2g(n)\ for\ all\ n \geq n_0$$ $$0 \leq c_1g(n) \leq f(n)\ for\ all\ n \geq n_0$$

which are the definitions of $f(n) = O(g(n))$ and $f(n) = \Omega(g(n))$. So we proved the hypothesis is wrong, thus we proved the "only if" part.

3.1-6

It's similiar to 3.1-5, the worst-case and best-case running time denote the upper bound and lower bound, which are $O(g(n))$ and $\Omega(g(n))$. So the proof is similar.

3.1-7

Let's let $f(n) = o(g(n))$ and $h(n) = \omega(g(n))$. According to the definition, for any positive constants $c_1$, $c_2$, there exist positive constants $n_1$, $n_2$ such that:

$$0 \leq f(n) < c_1g(n)\ for\ all\ n \geq n_1$$ $$0 \leq c_2g(n) < h(n)\ for\ all\ n \geq n_2$$

Suppose $o(g(n)) \cap \omega(g(n))$ is not empty, so at least we have one f(n) and one h(n) such that f(n) = h(n), because $c_1$ and $c_2$ are any positive constants, so we let $c_1 = c_2 = c$, and let $n_0 = max(n_1, n_2)$, so we have:

$$0 \leq f(n) < cg(n)\ for\ all\ n \geq n_0$$ $$0 \leq cg(n) < f(n)\ for\ all\ n \geq n_0$$

which also means:

$$0 \leq cg(n) < f(n)\ < cg(n)\ for\ all\ n \geq n_0$$

And we know the above inequation is impossible. So the hypothesis is wrong, thus $o(g(n)) \cap \omega(g(n))$ is empty.

3.1-8

$$\begin{aligned} \Omega(g(n, m)) = & \lbrace f(n, m): \text {there exist positive constants } c, n_0, \text {and } m_0 \text{ such that } \\ & 0 \leq cg(n, m) \leq f(n, m) \text{ for all } n \geq n_0 \text{ or } m \geq m_0 \rbrace \end{aligned}$$

$$ \begin{aligned} \Theta(g(n, m)) = & \lbrace f(n, m): \text {there exist positive constants } c_1, c_2, n_0, \text {and } m_0 \text{ such that } \\ & 0 \leq c_1g(n, m) \leq f(n, m) \leq c_2g(n, m) \text{ for all } n \geq n_0 \text{ or } m \geq m_0 \rbrace \end{aligned} $$