# Disproving asymptotic relation

I'm trying to disprove that $\forall f: N\rightarrow R^+,\forall g: N\rightarrow R^+, f \in \Omega(g) \iff \lfloor f\rfloor \in \Omega(\lfloor g\rfloor).$

However I need some hints.

-

## migrated from cs.stackexchange.comNov 19 '12 at 22:21

This question came from our site for students, researchers and practitioners of computer science.

What do you have so far ? – Bartek Nov 10 '12 at 22:04
@Bartek First I was trying to prove it using chains of inequalities: For the implication in the forward direction I came up with: [f]+1 >= f >= g >= [g] For the implication in the reverse direction I came up with: f >= [f] >= [g] >= g-1 However, I came out with nothing. Then I tried to disprove it, but it seems I need a counterexample (two functions) to disprove either the implication in the reverse direction or in the forward direction. But I couldn't think of the two functions. – oksana Nov 10 '12 at 22:46
Hint: There are constant functions $f,g$ which form a counterexample. – Yuval Filmus Nov 10 '12 at 23:12
@Yuval Filmus Thank you! I have the two functions now: f(n) = 0.25, g(n) = 1 – oksana Nov 10 '12 at 23:20
@YuvalFilmus: Really, I think the statement is true for $f=\Omega(g)$ and $g$ and $f$ constant functions. – A.Schulz Nov 11 '12 at 7:55

I disproved it by a counterexample (two functions) to disprove the implication in the forward direction. If $f(n) = 0.25$ and $g(n) = 1$, then $f \geq 0.25 g(n)$ for all $n$, which shows $f \in \Omega(g)$. However, $\lfloor f(n) \rfloor = 0$, and $\lfloor g(n) \rfloor = 1$, thus $\lfloor f(n) \rfloor$ is not in $\Omega(\lfloor g(n) \rfloor)$.
Whether or not the last statement is true depends on the precise definition of $\Omega$ at hand. $0$ is a wicked corner-case for some variants but not for others. – Raphael Nov 26 '12 at 12:10