1

I want to prove the following by definition of asymptotic notation
$$\Omega(n\cdot f(n)) = n\cdot \Omega(f(n))$$ Any suggestions?

user2976686
  • 185
  • 8

1 Answers1

1

Assuming that you have a definition that involves a positive values $\epsilon$, a constant $c$, and a constant $N$, you do the following:

write out what it means for a function $g$ to be in $Omega(f(n))$; then observe that the same values of $c$ and $N$ show that $n \mapsto n \cdot g(n)$ is in $\Omega(n \cdot f(n))$. That'll show that $n \cdot \Omega(f(n)) \subset \Omega(n \cdot f(n))$. Then you do almost exactly the same thing to show the reverse inclusion.

John Hughes
  • 93,729
  • ,$$g(n)\in \Omega(f(n)) \rightarrow \exists c \exists N_{0} \forall N>N_{0} \rightarrow g(n)>c\cdot f(n)$$ now what? – user2976686 Mar 30 '14 at 16:49
  • OK. And the final inequality can be multiplied by $n$ on both sides (why?). That shows that $n \cdot g(n) \in \Omega(n cdot f(n))$. So you're half done. Now you just have to do the other direction. – John Hughes Mar 31 '14 at 01:45