0

Can we say that the following condition is true? Why? $$ \Omega(O(f(n))) = O(\Omega(f(n))) $$

fhm
  • 135
  • 4
    What do you mean by $\Omega(O(f(n))$ and vice-versa? As far as I know it doesn't make much sense to compose asymptotic notations. – Luke Collins Sep 18 '17 at 00:09
  • 1
    @LukeCollins perhaps the inner asymptote is a function whereas the outer layer denotes a family of functions. – Vim Sep 18 '17 at 00:22

2 Answers2

1

The notation $O(f(n))$ can mean one of two things:

  • A set of functions: in this case, the set of all functions $g(n)$ for which there exists a constant $C$ such that for sufficiently large $n$, $g(n) \le C f(n)$. Here, writing $\binom n2 = O(n^2)$ is abuse of notation and should strictly speaking be written $\binom n2 \in O(n^2)$.
  • An unnamed function that is an element of this set. This makes writing $\binom n2 = O(n^2)$ okay, as well as more complicated statements such as $3^n = 2^{O(n)}$.

The corresponding interpretations exist for $\Omega(f(n))$ as well.

If we restrict ourselves to the first use of the notation, then $\Omega(O(f(n))$ and $O(\Omega(f(n))$ simply don't make sense: they're a "type error".

If we allow the second use of the notation, then $\Omega(O(f(n))$ is valid, but not an interesting object. Specifically, as long as $f(n) \ge 0$ for all sufficiently large $n$, we have $0 \in O(f(n))$. For any other function $g(n)$, as long as $g(n) \ge 0$ for all sufficiently large $n$, we have $g(n) = \Omega(0)$, and therefore we can say $g(n) = \Omega(O(f(n))$.

Under the same assumptions on $f(n)$ and $g(n)$, we also have $f(n) + g(n) \in \Omega(f(n))$ and $g(n) \in O(f(n)+g(n))$, making $g(n) = O(\Omega(f(n))$ also a thing we can say nearly all the time.

So, in that case, yes, it's true that $\Omega(O(f(n)) = O(\Omega(f(n))$, sort of, but you'd never talk about these things, because they're not useful.

Misha Lavrov
  • 142,276
1

I'll assume you're using the Knuth version of $\Omega$ rather than the Hardy-Littlewood version.

Presumably, $g(n) = \Omega(O(f(n)))$ would be shorthand for: there is some $h$ such that $h(n) = O(f(n))$ and $g(n) = \Omega(h(n))$, i.e. $h(n) = O(g(n)$. But that would be true for all $g$, since you could take $h(n) = \min(|f(n)|, |g(n)|)$$.

Similarly, $g(n) = O(\Omega(f(n))$ would be shorthand for: there is some $h$ such that $h(n) = \Omega(f(n))$, i.e. $f(n) = O(h(n))$, and $g(n) = O(h(n))$. Again, this is true for all $g$, e.g. you could take $h(n) = |f(n)| + |g(n)|$.

So yes, they are the same, but rather trivial.

Robert Israel
  • 448,999