0

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.

  • 2
    What do you have so far ? –  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. –  Nov 10 '12 at 22:46
  • 2
    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 –  Nov 10 '12 at 23:20
  • 1
    @YuvalFilmus: Really, I think the statement is true for $f=\Omega(g)$ and $g$ and $f$ constant functions. – A.Schulz Nov 11 '12 at 07:55
  • @oksana So you solved it? – phant0m Nov 11 '12 at 09:16
  • Yes I did. If f(n) = 0.25 and g(n) = 1, then f >= 0.25*g(n) for all n, which shows f is in Omega(g). However, floor(f(n)) = 0, and floor(g(n)) = 1, thus floor(f) is not in Omega(floor(g)). –  Nov 11 '12 at 13:36
  • Please update your question with your early attempts, and post an answer with your final solution. – Raphael Nov 12 '12 at 11:29
  • @A.Schulz That depends on the definition of $\Omega$ and the set of functions it admits. – Raphael Nov 12 '12 at 11:30

1 Answers1

2

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)$.

Raphael
  • 2,720
oksana
  • 31
  • 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