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

Some authors define $\Omega$ in a slightly different way than we do; let's use ${\Omega}^{\infty}$ (read "omega infinity") for this alternative definition. We say that $f(n) = {\Omega}^{\infty}(g(n))$ if there exists a positive constant $c$ such that $f(n) \ge cg(n) \ge 0$ for infinitely many integers $n$.

a. Show that for any two functions $f(n)$ and $g(n)$ that are asymptotically nonnegative, either $f(n) = O(g(n))$ or $f(n) = {\Omega}^{\infty}(g(n))$ or both, whereas this is not true if we use $\Omega$ in place of ${\Omega}^{\infty}$.

b. Describe the potential advantages and disadvantages of using ${\Omega}^{\infty}$ instead of $\Omega$ to characterize the running times of programs.

Some authors also define $O$ in a slightly different manner; let's use $O'$ for the alternative definition. We say that $f(n) = O'(g(n))$ if and only if $|f(n)| = O(g(n))$.

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

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

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

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

a. We have

$$ f(n) = \begin{cases} O(g(n)) \text{ and } {\Omega}^{\infty}(g(n)) & \text{if $f(n) = \Theta(g(n))$}, \\ O(g(n)) & \text{if $0 \le f(n) \le cg(n)$}, \\ {\Omega}^{\infty}(g(n)) & \text{if $0 \le cg(n) \le f(n)$, for infinitely many integers $n$}. \end{cases} $$

If there are only finite $n$ such that $f(n) \ge cg(n) \ge 0$. When $n \to \infty$, $0 \le f(n) \le cg(n)$, i.e., $f(n) = O(g(n))$.

Obviously, it's not hold when we use $\Omega$ in place of ${\Omega}^{\infty}$.

b.

• Advantages: We can characterize all the relationships between all functions.
• Disadvantages: We cannot characterize precisely.

c. For any two functions $f(n)$ and $g(n)$, we have if $f(n) = \Theta(g(n))$ then $f(n) = O'(g(n))$ and $f(n) = \Omega(g(n))$ and $f(n) = \Omega(g(n))$.

But the conversion is not true.

d. We have

$$ \begin{aligned} \tilde\Omega(g(n)) = \{f(n): & \text{ there exist positive constants $c$, $k$, and $n_0$ such that } \\ & \text{ $0 \le cg(n)\lg^k(n) \le f(n)$ for all $n \ge n_0$}.\} \end{aligned} $$

$$ \begin{aligned} \tilde{\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 c_1 g(n) \lg^{k_1}(n) \le f(n)\le c_2g (n) \lg^{k_2}(n)$ for all $n\ge n_0$.}\} \end{aligned} $$

For any two functions $f(n)$ and $g(n)$, we have $f(n) = \tilde\Theta(g(n))$ if and only if $f(n) = \tilde O(g(n))$ and $f(n) = \tilde\Omega(g(n))$.