Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

migrated from cs.stackexchange.com Nov 19 '12 at 22:21

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

2  
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
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 –  oksana 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 7:55

1 Answer 1

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.