Results 1 to 12 of 12

Thread: help me to prove this algorithm analysis

  1. #1
    Member
    Joined
    Jun 2007
    Posts
    77

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by EquinoX View Post
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jun 2007
    Posts
    77
    actually I did, lets start with no. 2 first.

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by EquinoX View Post
    actually I did, lets start with no. 2 first.

    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jun 2007
    Posts
    77
    Quote Originally Posted by CaptainBlack View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by EquinoX View Post
    okay, thanks how about number 1 now? it's kind of hard to proof
    Just write out the two definitions please.

    RonL
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by EquinoX View Post
    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))

    please.

    RonL
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Jun 2007
    Posts
    77
    Quote Originally Posted by EquinoX View Post
    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
    Quote Originally Posted by CaptainBlack View Post
    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

    please.

    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by EquinoX View Post
    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
    Attached Thumbnails Attached Thumbnails help me to prove this algorithm analysis-gash.png  
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Jun 2007
    Posts
    77
    Quote Originally Posted by CaptainBlack View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member
    Joined
    Jun 2007
    Posts
    77
    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?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    5
    Quote Originally Posted by EquinoX View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algorithm Analysis
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: Jul 1st 2009, 05:02 AM
  2. (Another) Algorithm Analysis
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: Jun 9th 2009, 02:30 AM
  3. Algorithm analysis
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: Jun 4th 2009, 05:29 AM
  4. Algorithm Analysis - Big-oh, etc...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Feb 8th 2009, 09:18 AM
  5. Algorithm analysis
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Jan 17th 2009, 08:32 AM

Search Tags


/mathhelpforum @mathhelpforum