# growth function and prove 2

• Nov 27th 2009, 02:25 AM
isiksoy7
growth function and prove 2
Can you help for the prove of this question ?
• Nov 27th 2009, 03:10 AM
emakarov
To solve this question you need two things: (1) to know the definitions of big-O and $\displaystyle \Omega$, and (2) to actually understand them, so that they make sense to you. I remember when I first learned about big-O and similar things, the definitions were just strings of symbols. I knew what each symbol meant and I could manipulate them formally, but I had no mental picture. For example, I could not say, "Well, this function grows infinitely, so it looks like it is bounded from below by this other function. Let me now find the actual constants from the definition of $\displaystyle \Omega$". It takes staring at the definition for some time, trying different examples, etc., before you actually "get it".

So, to start, could you write the definitions of big-O and $\displaystyle \Omega$ and describe what your difficulty is?
• Nov 27th 2009, 07:19 AM
isiksoy7
Big-0(Omega): Let f and g be functions from the set of integer or the set of real numbers to the set of real numbers.We say that f(x) is O(g(x)) if there are constants C and k such that |f(x)|<C|g(x)| where x>k

Big-Theta: Let f and g be functions from the set of integer or the set of real numbers to the set of real numbers.We say that f(x) is Ω (g(x)) if there are positive constants C and k such that |f(x)|>C|g(x)| where x>k
• Nov 27th 2009, 07:29 AM
emakarov
Excellent. Well, the definitions basically say that [$\displaystyle f\in O(g)$ with constants $\displaystyle C, k$] is the same thing as [$\displaystyle g\in\Omega(f)$ with constants $\displaystyle 1/C,k$].

Trivia: $\displaystyle \Omega$ is called Omega, where the stress is on the second syllable. It means "O mega", i.e., big O in Greek. This is opposed to "o micron", which is small o. Omicron is written in the same way as latin "o". Big Theta is written $\displaystyle \Theta$.
• Nov 27th 2009, 10:25 AM
isiksoy7
[IMG]file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/moz-screenshot-1.png[/IMG]Today I try to solve this prove but ı can't do that (Doh) and I am very tired now. If you help me to solve this problem , I will be very happy.
• Nov 27th 2009, 10:29 AM
emakarov
I think you will easily get it after rest. There is nothing to be done here; the most difficult fact is that $\displaystyle |a|<C|b|$ if and only if $\displaystyle |b|>(1/C)|a|$.