Results 1 to 12 of 12

Math Help - 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 \Omega(f(n))
    2. Show that  n^2 is \omega (n)
    3.  \sum_{i = 1}^n i^2 is 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
    4
    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 \Omega(f(n))
    2. Show that  n^2 is \omega (n)
    3.  \sum_{i = 1}^n i^2 is 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
    4
    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
    4
    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
    4
    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 \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 \Omega(f(n))
    2. Show that  n^2 is \omega (n)
    3.  \sum_{i = 1}^n i^2 is 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 \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 \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
    4
    Quote Originally Posted by EquinoX View Post
    O(n) is f(n) < c * g(n) and \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 f(n)=O(g(n)) implies the existance of a C and n_0 such that the condition for 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 f(n)=O(g(n)) implies the existance of a C and n_0 such that the condition for 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 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
    4
    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 ( \Omega(f(n)). This is proving the "only if" part.

    Then assume g(n) is ( \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 ( \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: July 1st 2009, 05:02 AM
  2. (Another) Algorithm Analysis
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: June 9th 2009, 02:30 AM
  3. Algorithm analysis
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: June 4th 2009, 05:29 AM
  4. Algorithm Analysis - Big-oh, etc...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 8th 2009, 09:18 AM
  5. Algorithm analysis
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 17th 2009, 08:32 AM

Search Tags


/mathhelpforum @mathhelpforum