3-6 Variations on $O$ and $\Omega$

Some authors define $\Omega$-notation in a slightly different way than this textbook does. We'll use the nomenclature $\stackrel{\infty}{\Omega}$ (read "omega infinity") for this alternative definition. We say that f(n) = $\stackrel{\infty}{\Omega}(g(n))$if there exists a positive constant $c$ such that $f(n) \geq cg(n) \geq 0$ for infinitely many integers n.

a. Show that for any two asymptotically nonnegative functions $f(n)$ and $g(n)$, we have $f(n)=O(g(n))$ or $f(n)=\stackrel{\infty}{\Omega}(g(n))$ (or both).

b. Show that there exist two asymptotically nonnegative functions $f(n)$ and $g(n)$ for which neither $f(n) = O(g(n))$ nor $f(n) = \Omega(g(n))$ holds.

c. Describe the potential advantages and disadvantages of using $\stackrel{\infty}{\Omega}$-notation instead of $\Omega$-notation to characterize the running times of programs.

Some authors also define $O$ in a slightly different manner. We’ll use $O'$ for the alternative definition: $f(n)=O'(g(n))$ if and only if $|f(n)|=O(g(n))$.

d. What happens to each direction of the "if and only if" in Theorem 3.1 on page 56 if we substitute $O'$ for $O$ but still use $\Omega$?

Some authors define $\tilde{O}$(read "soft-oh") to mean O with logarithmic factors ignored:

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

e. Define $\tilde{\Omega}$ and $\tilde{\Theta}$ in a similar manner. Prove the corresponding analog to Theorem 3.1.

a

$$ \begin{aligned} \text{if } f(n)\neq O(g(n))\cr \text{there must be infinite integers that }f(n) \geq cg(n)\geq 0\cr \text{otherwise choose the last } n = \text{ that } f(n)\geq cg(n) \text{ as } n_0\cr \text{for all }n\geq n_0,f(n)\leq cg(n)\implies f(n)=O(g(n))\cr \end{aligned} $$

b

$f(n)=n|\sin n|,g(n)=1$

c

• advantages: By a we can know that $O$ and $\stackrel{\infty}{\Omega}$ can characterize relationship between any two function.
• disadvantages: Not precise.

d

$$ \begin{aligned} \forall f(n) , g(n):\cr f(n)=\Theta(g(n)) \implies f(n)=\Omega(g(n)) \And f(n)=O'(g(n))\cr \text{but the conversion is not true} \end{aligned} $$

e

$$ \begin{aligned} \tilde\Omega(g(n))=\lbrace f(n): & \text{ there exist positive constants }c,k,\text{ and } n_0 \text{ such that}\cr & 0\leq f(n) \leq cg(n)\lg^{k}(n) \text{ for all }n \geq n_0\rbrace .\cr \tilde\Theta(g(n))=\lbrace f(n): & \text{ there exist positive constants }c_1,c_2,k,\text{ and } n_0 \text{ such that}\cr & 0\leq c_1g(n)\lg^{k}(n)\leq f(n) \leq c_2g(n)\lg^{k}(n) \text{ for all }n \geq n_0\rbrace .\cr \text{according to there definity: } & f(n)=\tilde\Theta(g(n))\iff f(n)=\tilde O(g(n)) \And f(n)=\tilde\Omega (g(n))\cr \end{aligned} $$