1. ## 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!

2. 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, $$C\sqrt{n}$$ would never have the required property for big O.

3. Originally Posted by yoonsi
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

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

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.

5. Originally Posted by CaptainBlack
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
Originally Posted by yoonsi
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

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