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))$.