Variations of \(O\) and \(\Omega\)
Some authors define \(\Omega\) in a slightly different way than we do; let’s use \(\mathop \Omega \limits^\infty\) (read “omega infinity”) for this alternative definition. We say that \(f(n) = \mathop \Omega \limits^\infty(g(n))\) if there exists a positive constant \(c\) such that \(f(n) \geq cg(n) \geq 0\) for infinitely many integers \(n\).
Show that for any two functions \(f(n)\)and \(g(n)\) that are asymptotically nonnegative, either \(f(n) = O(g(n))\) or \(f(n) = \mathop \Omega \limits^\infty(g(n))\) or both, whereas this is not true if we use \(\Omega\) in place of \(\mathop \Omega \limits^\infty\).
Describe the potential advantages and disadvantages of using \(\mathop \Omega \limits^\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 \(\vert f(n) \vert = O(g(n))\).
- What happens to each direction of the “if and only if” in Theorem 3.1 if we substitute \(O'\) for \(\) but still use \(\Omega\)?
Some authors define \(\widetilde{O}\) (read “soft-oh”) to mean \(O\) with logarithmic factors ignored:
\[\begin{aligned}\widetilde{O}(g(n)) = \{ f(n) : &\text { there exists positive constants }c, k, \text { and } n_0 \\ &\text { such that } 0 \leq f(n) \leq cg(n)\lg^k(n) \text { for all } n \geq n_0 \}\end{aligned}\]
- Define \(\widetilde{\Omega}\) and \(\widetilde{\Theta}\) in a similar manner. Prove the corresponding analog to Theorem 3.1.
A. Asymptotic Non-negative Functions
Notice that if a function is asymptotically non-negative, only information we know about the function is that: asymptotically it’ll never be less than zero. However, it can either be monotonically increasing, or a positive contestant, or it can even oscillate between increasing decreasing.
For example, consider the functions \(f(n) = 2\) and \(g(n) = 2 + sin(n)\).
The below graph shows the functions, \(f(n)\) in green and \(g(n)\) in blue.
As it is evident from the graphs, asymptotically, both are non-negative.
Also for infinitely many integers \(n\), \(f(n) \geq cg(n) \geq\), for positive constant \(c = 1\), i.e. \(f(n) = \mathop \Omega \limits^\infty(g(n))\). This happens whenever the blue graph is below the green one, and there is infinitely many such scenarios.
However, as per definition of \(O\) or \(\Omega\), \(f(n)\) is neither \(O(g(n))\) nor \(\Omega(g(n))\).
B. Advantage and Disadvantage
This directly follows from the previous section: the advantage being we can establish a relationship between any two functions, and the disadvantage being some of those relationships might not be precise enough to be of any use.
C. Substitution for Big-O
\(\vert f(n) \vert = O(g(n))\) implies \(0 \leq \vert f(n) \vert \leq cg(n)\)
As long as \(f(n) \geq 0\), there is no difference between \(O\) and \(O'\). But when \(f(n) < 0\), \(O\) notation does not cover such functions, but \(O'\) does.
With this difference, there is no change in the “if” part but we cannot use the “only if” part anymore as we will need to use negative multiplier constants to find lower limit when \(f(n) < 0\).
D. Ignoring Logarithmic Factors
As logarithmic functions are monotonically increasing, \(\widetilde{\Omega}\) and \(\widetilde{\Theta}\) can be defined similarly and theorem 3.1 can be restated without any other changes.