# Thread: help me to prove this algorithm analysis

1. ## help me to prove this algorithm analysis

How do you proof that:

1. Show that f(n) is O(g(n)) if and only if g(n) is $\displaystyle \Omega(f(n))$
2. Show that $\displaystyle n^2$ is $\displaystyle \omega (n)$
3. $\displaystyle \sum_{i = 1}^n i^2$ is $\displaystyle O(n^3)$

I am really confused on doing this, can someone help me

2. Originally Posted by EquinoX
How do you proof that:

1. Show that f(n) is O(g(n)) if and only if g(n) is $\displaystyle \Omega(f(n))$
2. Show that $\displaystyle n^2$ is $\displaystyle \omega (n)$
3. $\displaystyle \sum_{i = 1}^n i^2$ is $\displaystyle O(n^3)$

I am really confused on doing this, can someone help me
Have you looked at the definitions of big-O, big-Omega, small-omega notation?

You will find them here (about three quarters of the way down the page).

RonL

for this problem f(n) is n^2 and g(n) is n

and according to the definition of little omega

g(n) <= c * f(n), for all n>n0 and c>0

but how do I a value of n0 so that this is true?? that's my concern

4. Originally Posted by EquinoX

for this problem f(n) is n^2 and g(n) is n

and according to the definition of little omega

g(n) <= c * f(n), for all n>n0 and c>0

but how do I a value of n0 so that this is true?? that's my concern
Take c=1, and n0=1, since for all n>1

n<= n^2

RonL

5. Originally Posted by CaptainBlack
Take c=1, and n0=1, since for all n>1

n<= n^2

RonL
okay, thanks how about number 1 now? it's kind of hard to proof

6. Originally Posted by EquinoX
okay, thanks how about number 1 now? it's kind of hard to proof
Just write out the two definitions please.

RonL

7. Originally Posted by EquinoX
okay, thanks how about number 1 now? it's kind of hard to proof
Just write out the two definitions for

f(n) is O(g(n))

and

g(n) is $\displaystyle \Omega$(f(n))

RonL

8. Originally Posted by EquinoX
How do you proof that:

1. Show that f(n) is O(g(n)) if and only if g(n) is $\displaystyle \Omega(f(n))$
2. Show that $\displaystyle n^2$ is $\displaystyle \omega (n)$
3. $\displaystyle \sum_{i = 1}^n i^2$ is $\displaystyle O(n^3)$

I am really confused on doing this, can someone help me
Originally Posted by CaptainBlack
Just write out the two definitions for

f(n) is O(g(n))

and

g(n) is $\displaystyle \Omega$(f(n))

yes I solved this one finely by using both of the definitions

RonL
O(n) is f(n) < c * g(n) and $\displaystyle \Omega (n)$ is g(n) >= c * f(n) therefore if we combine both statement the statement above is true right?

9. Originally Posted by EquinoX
O(n) is f(n) < c * g(n) and $\displaystyle \Omega (n)$ is g(n) >= c * f(n) therefore if we combine both statement the statement above is true right?
The attachment shows the definitions (courtesy of Wikipedia).

That $\displaystyle f(n)=O(g(n))$ implies the existance of a $\displaystyle C$ and $\displaystyle n_0$ such that the condition for $\displaystyle g(n)=\Omega (n)$ apply and vice versa

RonL

10. Originally Posted by CaptainBlack
The attachment shows the definitions (courtesy of Wikipedia).

That $\displaystyle f(n)=O(g(n))$ implies the existance of a $\displaystyle C$ and $\displaystyle n_0$ such that the condition for $\displaystyle g(n)=\Omega (n)$ apply and vice versa

RonL
hmm..so I guess I did this wrong. why is f(n) < c * g(n) and g(n) < c * f(n) implies an existence? can you explain this a bit further?? does this mean by the definition that f(n) < c * g(n) and g(n) < c * f(n) gives the right condition for c and $\displaystyle n_0$ to be true, which is c > 0 and n>n0?

11. My instructor says that I have to proof this in two steps one is the if part and the other one is the only if. How do I do this?

12. Originally Posted by EquinoX
My instructor says that I have to proof this in two steps one is the if part and the other one is the only if. How do I do this?
Assume f(n) is O(g(n) then prove this implies that g(n) is ($\displaystyle \Omega(f(n))$. This is proving the "only if" part.

Then assume g(n) is ($\displaystyle \Omega(f(n))$ then prove this implies that f(n) is O(g(n). This is the "if" part.

Together they prove that f(n) is O(g(n) if and only if g(n) is ($\displaystyle \Omega(f(n))$

(Both of these are implicit in what we discussed in the earlier posts)

RonL