Skip to content

3.2Asymptotic notation formal definitions

3.2-1

Let $f(n)$ and $g(n)$ be the asympotically nonnegative functions. Using the basic definition of $\Theta$-notation, prove that max ${f(n),g(n)} = \Theta (f(n) + g(n))$.

$$ \begin{aligned} \text{Let } n_0 \text{ be a value that makes f(n) greater than 0 for n >}n_0\cr \text{Then for }n>n_0\cr \frac 1 2 (f(n)+g(n)) \leq \max(f(n),g(n)) \leq 1(f(n)+g(n))\cr \max(f(n),g(n))=\Theta(f(n)+g(n))\cr \end{aligned} $$

Tips: I will omit details like "$\text{Let } n_0 \text{ be a value that makes f(n) greater than 0 for n >}n_0$""$\exist c,n_0$" and "for $n > n_0$" for convenience from here.

3.2-2

Explain why the statement, "The running time of algorithm A is at least $O(n^2)$,"if meaningless.

$A = O(n^2)$ means $\exist n_0,c:A \leq cn^2$ for $n>n_0$.

$A$ is at least $O(n)$ means $A \geq \text{a function that }\leq cn^2$

You can say A can be any function or no function. Both are meaningless.

3.2-3

Is $2^{n+1}=O(2^n)$? Is $2^{2n}=O(2^n)$?

  • $2^{n+1} \leq 2*2^n$, Yes
  • $2^{2n} \leq c \cdot 2^n \text{ implies } c \geq 2^n$, no constant satisfies it. No

3.2-4

Prove Theorem 3.1.

$$ \begin{aligned} & f(n) = O(g(n)) \quad and \quad f(n)=\Omega(g(n))\cr & \implies c_1 g(n)\leq f(n) \leq c_2g(n)\cr & \implies f(n) = \Theta(g(n))\cr & f(n) = \Theta(g(n))\cr & \implies c_1 g(n)\leq f(n) \leq c_2g(n)\cr & \implies f(n) = O(g(n)) \quad and \quad f(n)=\Omega(g(n))\cr \end{aligned} $$

We have $f(n) = \Theta(g(n))$ if and only if $f(n) = \Omega(g(n))$ and $f(n) = O(g(n))$

3.2-5

Prove that the running time of an algorithm is $\Theta(g(n))$ if and only if its worst-case running time $O(g(n))$ and its best-casse running time is $\Omega (g(n))$.

$$ \begin{aligned} A=\Theta(g(n)) & \implies c_1 g(n) \leq A \leq c_2 g(n) \text{ for all cases}\cr & \implies \text{worst-case running time}= O(n)\cr & \And \text{best-case running time}=\Omega(g(n))\cr \text{worst-case running time}= O(n) & \implies A \leq c_2 g(n) (1)\cr \text{best-case running time}=\Omega(g(n)) & \implies c_1 g(n) \leq A (2)\cr (1) \And (2) & \implies A=\Theta(g(n))\cr \end{aligned} $$

3.2-6

Prove that $o(g(n)) \cap \omega (g(n))$ is empty set.

$f(n) < cg(n) \And f(n) > c(g(n)) \implies NIL$

3.2-7

We can extend our notation to the case of two parameters n and m that can go to $\infty$ independently at different rates. For a given function $g(n,m)$, we denote by $O(g(n,m))$ the set of functions

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

Give corresponding definitionss for $\Omega(g(n,m))$ and $\Theta(g(n,m))$.

$$ \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 \cr & \text{ such that } 0 \leq c_1g(n,m)\leq f(n, m) \leq c_2g(n, m)\cr & \text{ for all } n \geq n_0 \text{ or } m \geq m_0.\rbrace\cr \Omega(g(n, m)) =\lbrace f(n, m): & \text{ there exist positive constants } c, n_0, \text{ and } m_0 \cr & \text{ such that } 0 \leq cg(n,m)\leq f(n, m)\cr & \text{ for all } n \geq n_0 \text{ or } m \geq m_0.\rbrace\cr \end{aligned} $$