# Thread: growth function and prove 2

1. ## growth function and prove 2

Can you help for the prove of this question ?

2. 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?

3. 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

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

5. [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 and I am very tired now. If you help me to solve this problem , I will be very happy.

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