3-5

3-5 Variations on O and $\Omega$
Some authors define $\Omega$ in a slightly different way than we do; let’s use $ \overset{\infty}{\Omega}$ (read “omega infinity”) for this alternative definition. We say that f(n) = O(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 functions f(n) and g(n) that are asymptotically nonnegative, either f(n) = O(g(n)) or $f(n)= \overset{\infty}{\Omega}(g(n))$ or both, whereas this is not true if we use $\Omega$ in place of $\overset{\infty}{\Omega}$

b. Describe the potential advantages and disadvantages of using $\overset{\infty}{\Omega}$ 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 still use $\Omega$ ?

Some authors define $\tilde{O}$ (read “soft-oh”) to mean O with logarithmic factors ignored: $\tilde{O}(g(n)) = \{ f(n): $ there exist positive constants c, k, and n0 such that

                   $0 \leq f(n) \leq c g(n) \lg^{k}(n) $for all $n \geq n0$ }.

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


Solution:
a. Lets define f(n) = O(g(n)) $0 \leq f(n) \leq c g(n)$ where c is a positive constant for all $n \geq n_0$. Now if we see $f(n)= \overset{\infty}{\Omega}(g(n))$ this does'nt define $n \geq n_0$ it considers infinite numbers.

b. The advantage is \overset{\infty}{\Omega} defines lower bound for every possible numbers of elements as input.

c. The direction is not affected because $f(n) = O^{'}(g(n))$ if and only if $|f(n)| = O(g(n))$. this means $ 0 \geq |f(n)| \geq c g(n)$ since we cannot substitue negative value for n(bcoz we cannot negative no of elements as input to algorithm). The above equation can be written as $ 0 \geq f(n) \geq c g(n)$ which is similar to $f(n) = O(g(n))$ d. $\tilde{O}(g(n)) = \{ f(n): $ there exist positive constants c, k, and n0 such that

                   $0 \leq f(n) \leq c g(n) \lg^{k}(n) $for all $n \geq n0$ }.

$\tilde{\Omega}(g(n) = \{ f(n): $ there exist positive constants c, k, and n0 such that

                   $0 \leq c g(n) \lg^{k}(n)\leq f(n) $for all $n \geq n0$ }.

$\tilde{\theta}(g(n)) = \{ f(n): $ there exist positive constants $c_1$,$c_2$, k, and n0 such that

                   $0 \leq c_1 g(n) \lg^{k}(n)\leq f(n) \leq c_2 g(n) \lg^{k}(n) $for all $n \geq n0$ }.

since $\tilde{\theta}(g(n)) = \{ f(n)$ is $0 \leq c_1 g(n) \lg^{k}(n)\leq f(n) \leq c_2 g(n) \lg^{k}(n)$ separating the in equalities $$\begin{equation}0 \leq c_1 g(n) \lg^{k}(n)\leq f(n) \end{equation}$$
$$\begin{equation} 0 \leq f(n) \leq c_2 g(n) \lg^{k}(n) \end{equation}$$ equation $(1)$ is $\tilde{\Omega}(g(n) = f(n) $ and equation $(2)$ is $\tilde{O}(g(n)) = f(n) $
$\tilde{\theta}(g(n)) = f(n)$ if and only if $\tilde{\Omega}(g(n) = f(n) $ and $\tilde{O}(g(n)) = f(n) $ hence the theorem is proved.