Thread: Need help getting an intuitive idea of big-Omega notation

1. Need help getting an intuitive idea of big-Omega notation

Here is the definition I am going of of.
Let
f and g be real-valued functions defined on the same set of nonnegative real
numbers. Then
1.
f is of order at least g, written f(x) is Big-Omega(g(x)), if, and only if, there exist a
positive real number A and a nonnegative real number a such that A|g(x)| | f (x)| for all real numbers x > a.

So I am wondering why the constant A is multipled by g(x). Is it basically saying, "hey, at a certain point, it doesnt matter what you multiply g(x) by, because f(x) is so big that its gonna always be bigger then the multiple of g(x)".
Perhaps if someone could explain why x^2 is not Big-Omega(x) and that would help. I get how to solve problems it is jus the intuition I am missing.

2. Re: Need help getting an intuitive idea of big-Omega notation

Originally Posted by mdm508
Here is the definition I am going of of.
Let
f and g be real-valued functions defined on the same set of nonnegative real
numbers. Then
1.
f is of order at least g, written f(x) is Big-Omega(g(x)), if, and only if, there exist a
positive real number A and a nonnegative real number a such that A|g(x)| | f (x)| for all real numbers x > a.
I'm seeing the definition of $\mathcal{O}$ to be opposite what you've written

in otherwords

$f(x) \text{ is } \mathcal{O}(g(x)) \Leftrightarrow \exists A>0,~a>0 \ni |f(x)| \leq A |g(x)|,~x>a$

this might help some

https://www.cs.auckland.ac.nz/course...-lecture03.pdf

3. Re: Need help getting an intuitive idea of big-Omega notation

I am pretty sure the definition you provided is something else. I got that definition straight out of my book. Furthermore, the definition from the resource your provided is essentially the same as the one i provided.

"The function g(n) is Ω(f(n)) iff there exists a
positive real constant c and a positive integer n0
such that g(n) ≥ cf(n) for all n > n0" Slide 1

4. Re: Need help getting an intuitive idea of big-Omega notation

Originally Posted by mdm508
I am pretty sure the definition you provided is something else. I got that definition straight out of my book. Furthermore, the definition from the resource your provided is essentially the same as the one i provided.

"The function g(n) is Ω(f(n)) iff there exists a
positive real constant c and a positive integer n0
such that g(n) ≥ cf(n) for all n > n0" Slide 1
you've flipped the inequality sign

it says $g(n) \text{ is }\mathcal{O}(f(n)) \Leftrightarrow g(n) \leq c f(n),~n > n_0$

and you flipped it in your original post

5. Re: Need help getting an intuitive idea of big-Omega notation

Originally Posted by romsek
you've flipped the inequality sign

it says $g(n) \text{ is }\mathcal{O}(f(n)) \Leftrightarrow g(n) \leq c f(n),~n > n_0$

and you flipped it in your original post

suppose $x^2 \sim \mathcal{O}(x)$

Then $\exists A>0, a>0,~\ni x^2 \leq A x,~\forall x > a$

$x^2 - A x \leq 0,~\forall x > a$

$\left(x - \dfrac A 2\right)^2 - \dfrac {A^2}{4} \leq 0,~\forall x > a$

$\left(x - \dfrac A 2\right)^2 \leq \dfrac {A^2}{4} \leq 0,~\forall x > a$

the left side equals $\dfrac {A^2}{4}$ at $x = \dfrac{3A}{4}$ and increases as $x$ increases.

So it should be clear that this expression is false $\forall x > \dfrac{3A}{4}$

and thus $x^2 \text{ is not } \mathcal{O}(x)$

6. Re: Need help getting an intuitive idea of big-Omega notation

Originally Posted by romsek
you've flipped the inequality sign

it says $g(n) \text{ is }\mathcal{O}(f(n)) \Leftrightarrow g(n) \leq c f(n),~n > n_0$

and you flipped it in your original post
It is not $\mathcal{O}$-notation it is $\Omega$-notation. See here.

7. Re: Need help getting an intuitive idea of big-Omega notation

Originally Posted by Plato
It is not $\mathcal{O}$-notation it is $\Omega$-notation. See here.
Thanks.

I'll be downstairs....

in a pool of blood.