0

Iv'e been given this question:
let $f,g:\mathbb{N} \rightarrow \mathbb{N}$ be increasing monotonic functions.
Is it always true that $f\left( n\right) =\Omega ( g\left( n\right) )$ or $g\left( n\right) =\Omega ( f\left( n\right) )$ ?
I can give a counter example only when one of the functions is not increasing monotonic, but I couldn't find a counter example for which both $f, g$ are increasing monotonic.
On the other hand, I couldn't prove that it is true.
Would like to hear any suggestions

Tom Waller
  • 31
  • 2
    It's not true but it's pretty annoying to write down a counterexample explicitly. The idea is that you can alternate regions where $f(n)$ increases much faster than $g(n)$ with regions where $g(n)$ increases much faster than $f(n)$, in such a way that they technically stay strictly increasing the whole time but $f(n)$ spends some time arbitrarily larger than $g(n)$ and vice versa. – Qiaochu Yuan Oct 29 '22 at 18:32
  • 1
    What is the meaning of that $\Omega$ notation? Is it like Landau's $O$ notation? – ajotatxe Oct 29 '22 at 18:48
  • 1
    Does $f(n)=\Omega(g(n))$ mean $f(n)\geq C\cdot g(n)$ infinitely often? – Clayton Oct 29 '22 at 18:55
  • @Clayton yes, it is – Tom Waller Oct 29 '22 at 19:18
  • @Qiaochu Yuan can you give an example on how to build this functions? – Tom Waller Oct 29 '22 at 19:19
  • @Clayton It isn't "infinitely often." Rather it is "for all sufficiently large $n$." – angryavian Oct 29 '22 at 20:35
  • @angryavian There are various non-equivalent definitions for $\Omega$ but according to himself, Tom chose Hardy–Littlewood's definition, which is "infinitely often". – Anne Bauval Oct 29 '22 at 20:42
  • 1
    @AnneBauval My mistake, I was not aware of the Hardy-Littlewood definition. Thanks for pointing this out. – angryavian Oct 29 '22 at 20:46
  • 1
    Upon further reflection, I wonder if OP is really using the Landau definition, given that (a) they found a counterexample without the monotonicity constraint, and (b) the question is almost trivial under the Hardy-Littlewood definition (via Anne Buval's answer). Tom, could you double-confirm which definition you are using? – angryavian Oct 29 '22 at 20:52

1 Answers1

0

Since $\neg[f(n)=\Omega(g(n))]\Leftrightarrow f(n)=o(g(n)),$ we cannot have both $\neg[f(n)=\Omega(g(n))]$ and $\neg[g(n)=\Omega(f(n))].$ Hence the answer is: yes, it is always true that $f\left( n\right) =\Omega ( g\left( n\right) )$ or $g\left( n\right) =\Omega ( f\left( n\right) ).$

Anne Bauval
  • 34,650