0
$\begingroup$

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 ?2012-11-10
  • 0
    @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.2012-11-10
  • 2
    Hint: There are constant functions $f,g$ which form a counterexample.2012-11-10
  • 0
    @Yuval Filmus Thank you! I have the two functions now: f(n) = 0.25, g(n) = 12012-11-10
  • 1
    @YuvalFilmus: Really, I think the statement is true for $f=\Omega(g)$ and $g$ and $f$ constant functions.2012-11-11
  • 0
    @oksana So you solved it?2012-11-11
  • 0
    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)).2012-11-11
  • 0
    Please update your question with your early attempts, and post an answer with your final solution.2012-11-12
  • 0
    @A.Schulz That depends on the definition of $\Omega$ and the set of functions it admits.2012-11-12

1 Answers 1