Results 1 to 5 of 5

Math Help - Big-Oh algorithm Proof

  1. #1
    Newbie
    Joined
    Aug 2009
    Posts
    16

    Big-Oh algorithm Proof

    Hello everyone! I'm doing a stage 2 Algorithms paper and I've done most of these running time questions. However I'm stuck with doing a proof, and proofs just fly over my head. If someone could please step me through how to do this, I would appreciate it. Also, I'd appreciate being helped more than just given the answer, as that wouldn't really benefit me much :3

    At this point, I'm thinking I'd use a proof by contradiction... but... I don't know where to start. I have a similar question which I'm working through at the moment. I'll post it here when I'm done because if that one works out to be correct then I'll feel a lot more confident about this one.

    Formally prove that 0.1n +10 \sqrt{n} is not O(\sqrt{n}) using the definition of O only.

    P.S. I sincerly apologise if I have this in the wrong place. I was unsure of where else to place it.
    Thanks in advance for any help!
    Last edited by yoonsi; August 11th 2010 at 05:12 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jul 2010
    From
    Vancouver
    Posts
    432
    Thanks
    16
    I think this is in its right place! I think you are on the right track with this contradiction proof, because it should be relatively easy to show that it does not matter what constant [LaTeX ERROR: Convert failed] you choose, [Math]C\sqrt{n}[/tex] would never have the required property for big O.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by yoonsi View Post
    Hello everyone! I'm doing a stage 2 Algorithms paper and I've done most of these running time questions. However I'm stuck with doing a proof, and proofs just fly over my head. If someone could please step me through how to do this, I would appreciate it. Also, I'd appreciate being helped more than just given the answer, as that wouldn't really benefit me much :3

    At this point, I'm thinking I'd use a proof by contradiction... but... I don't know where to start. I have a similar question which I'm working through at the moment. I'll post it here when I'm done because if that one works out to be correct then I'll feel a lot more confident about this one.

    Formally prove that 0.1n +10 \sqrt{n} is not O(\sqrt{n}) using the definition of O only.

    P.S. I sincerly apologise if I have this in the wrong place. I was unsure of where else to place it.
    Thanks in advance for any help!
    Let f(n)=0.1n+10\sqrt{n} and suppose that f(n) \in O(\sqrt{n}). By definition of big-O notation this means that there exists a $$ N>0 and a constant $$ c>0 such that:

    |f(n)|\le c\sqrt{n},\ \forall n>N

    Now as everything is positive we can drop the |.| and have (note from here on I do not mention \forall  n>N but it is implied):

    0.1n+10\sqrt{n}\le c \sqrt{n}

    and so there exists a $$ k (which must be positive) such that:

    n \le k \sqrt{n}

    or that:

    \sqrt{n} \le k

    etc

    CB
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2009
    Posts
    16
    Thanks for the replies both of you. CaptainBlack, I'm trying to understand what you've written there and I'm struggling a bit. Would you mind elaborating on the steps? I'm horrendously weak at this. Also... my current understanding leads me to think you're proving that is IS big O? It's supposed to be proven that its NOT big O... although I think I've just missed the point entirely ;p

    Many thanks in advance!

    EDIT: Also, if anyone knows any online material I could read to practise this sort of stuff, I would greatly appreciate it if you could share it with me.
    Last edited by yoonsi; August 12th 2010 at 05:51 PM. Reason: Addition
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    Let f(n)=0.1n+10\sqrt{n} and suppose that f(n) \in O(\sqrt{n}). By definition of big-O notation this means that there exists a $$ N>0 and a constant $$ c>0 such that:

    |f(n)|\le c\sqrt{n},\ \forall n>N

    Now as everything is positive we can drop the |.| and have (note from here on I do not mention \forall  n>N but it is implied):

    0.1n+10\sqrt{n}\le c \sqrt{n}

    and so there exists a $$ k (which must be positive) such that:

    n \le k \sqrt{n}

    or that:

    \sqrt{n} \le k

    etc

    CB
    Quote Originally Posted by yoonsi View Post
    Thanks for the replies both of you. CaptainBlack, I'm trying to understand what you've written there and I'm struggling a bit. Would you mind elaborating on the steps? I'm horrendously weak at this. Also... my current understanding leads me to think you're proving that is IS big O? It's supposed to be proven that its NOT big O... although I think I've just missed the point entirely ;p

    Many thanks in advance!

    EDIT: Also, if anyone knows any online material I could read to practise this sort of stuff, I would greatly appreciate it if you could share it with me.
    The last line which in expanded form is:

    \sqrt{n} \le k\ \forall n>N

    is a contradiction so the premis (that f(n) \in O(\sqrt{n}) ) of the derivation is false.

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean Algorithm Proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 11th 2010, 04:16 AM
  2. Proof Shuttle Sort is a quadratic order algorithm.
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 11th 2010, 12:50 PM
  3. Euclidean algorithm proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: November 28th 2009, 07:03 PM
  4. An exponential proof and an algorithm
    Posted in the Algebra Forum
    Replies: 6
    Last Post: December 15th 2008, 07:03 AM
  5. Shuffling algorithm proof, please help!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 14th 2008, 04:21 PM

Search Tags


/mathhelpforum @mathhelpforum