# growth function

• Feb 2nd 2009, 10:08 AM
galactus
growth function
Hey All:

I am not sure where to post something like this.

I have encountered something I am not familiar with too well.

This is part of

determine rather this is true or not:

$\displaystyle f(n)\in {\Theta}(n^{3})$

$\displaystyle f(n)\in {\Omega}(n^{2})$

What does this stuff represent?.

Anyone have an idea?.

The theta is the asymptotic tight bound and the Omega is the asymptotic lower bound.
• Feb 3rd 2009, 07:45 AM
Laurent
Quote:

Originally Posted by galactus
Hey All:

I am not sure where to post something like this.

I have encountered something I am not familiar with too well.

This is part of

determine rather this is true or not:

$\displaystyle f(n)\in {\Theta}(n^{3})$

$\displaystyle f(n)\in {\Omega}(n^{2})$

What does this stuff represent?.

Anyone have an idea?.

The theta is the asymptotic tight bound and the Omega is the asymptotic lower bound.

You'll find every answer and more in this wikipedia article

In a word, $\displaystyle f(n)= \Omega(g(n))$ means "$\displaystyle g(n)= O(f(n))$" (and I had never seen it before), while $\displaystyle f(n)= \Theta(g(n))$ means "$\displaystyle f(n)= O(g(n))$ and $\displaystyle g(n)= O(f(n))$". In math, I think the notation $\displaystyle f(n)\asymp g(n)$ is more common than $\displaystyle f(n)=\Theta(g(n))$.