0

I'm currently studying Algorithms Design and Analysis and our teacher today started talking about Asymptotic Analysis. He said that, after choosing an arbitrary $c$, if you manage to find a $n_0$ that satisfies $f(n_0) \ge c*g(n)$, that in turn means that $g(n) \le f(n) \ \forall \ n > n_0$.

He gave this example:

Given $g(n) = n + 34\ $ and $f(n) = n$, is $g(n) = O(f(n))$?

$ n + 34 \le c*n \\ \text {let $c = 2$ } \\ n + 34 \le 2n \\ \text {if $n_0 = 34$, then} \\ \color {green} {68 \le 68} $

Since we got a valid inequation after finding 34, it is therefore true that $$g(n) \le c * f(n) \ \forall \ n > 34$$

That works for that example. However, take this curve, for instance (red is the $c * f(n)$ - the asymptote; blue is $g(n)$):

enter image description here

An almost identical one was even shown in the teacher's presentation. If we were to take the image's $n_0$ as our $n_0$ (as it was shown in the presentation), then the assertion would be correct. However, by using the teacher's method, I could come up with an arbitrary $c$ and find a $n_1$, therefore ending up with a valid pair of $(n_0, c)$ that satisfies the condition $f(n_0) \ge c*g(n)$; obviously, though, it would be wrong to conclude, in that case, that $g(n) \le c * f(n) \ \forall \ n > n_0$.

A similar thing could happen by analyzing a sinusoidal function.

The way I tried to resolve the example he gave was this:

$ n + 34 \le c*n \\ \text {let $c = 2$ } \\ n + 34 \le 2n \\ \color {green} {n \ge 34} $

I'm not really sure though if my solution is any different and if it would work in those cases I mentioned.

Is the teacher correct? If not, is my method any different? What is the correct way of proving a function $g(n)$ is $O(f(n))$?

Did
  • 279,727
andre_ss6
  • 101
  • 1
    Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! – Raphael Aug 29 '16 at 23:52
  • 2
    "g(n) = O(f(n)) ∀ n > n0" makes no sense. Either g(n) = O(f(n)) or it doesn't; there's no qualification on n. You might want to review the definition of big-O notation. Take a look at http://cs.stackexchange.com/q/57/755, http://cs.stackexchange.com/q/192/755, http://cs.stackexchange.com/q/824/755, and the chapter of your textbook where this is covered (or any textbook on algorithms), then work through your question again and edit it accordingly. Thank you! – D.W. Aug 30 '16 at 04:47
  • 1
    While this question is certainly on the mathematical end, we do consider questions about asymptotics to be ontopic here. Since you already got an answer which -- as far as I can tell -- has identified your problem quite aptly, why do you want the question to be migrated? – Raphael Aug 30 '16 at 16:00
  • I still don't understand how to correctly prove it and especially why such proof don't fall into the situation shown in the image (which is the entire point of my question). I know this may be a silly question, and the answer may be obvious to some of you, but it isn't to me. I want a better answer and it seems that this community won't provide one. I don't have rep to start a bounty, and questions on math usually seem to be answered more didactically. Those are all my reasons. – andre_ss6 Aug 30 '16 at 19:31
  • Did you look at some examples before asking? (But please change the title to something that does not mix symbols and English as the present one does.) – Did Aug 30 '16 at 21:45
  • @Did Yes, of course. Also, sorry but I'm not sure how to improve the title. – andre_ss6 Sep 01 '16 at 12:14
  • And the examples you looked at were not enough to completely answer this? – Did Sep 01 '16 at 15:07
  • I'm sorry, I really don't mean to be rude in any way, but I think it is obscenely obvious that they weren't enough for me to understand - otherwise I wouldn't have asked this - and I'm certain that you already knew that before even commenting. I haven't started using SE yesterday. I know I'm supposed to search and research before asking. Your comments aren't being helpful. If you think this question is not worth answering, feel free to forget you ever saw it. If you think there's something wrong with it, feel completely free to flag it. But please stop with these cynical comments. – andre_ss6 Sep 01 '16 at 16:35

1 Answers1

2

Your example with $n_1$ clearly shows that what your teacher said was wrong (or that you misinterpreted what your teacher said in a way that made it wrong). Establishing that $68\geq68$ cannot possibly establish any property of a function for sufficiently large $n$.

However, your attempt is also incorrect. You've started with the assumption that $f(n)\geq c\,g(n)$ and concluded that $n\geq 34$, which is backwards. You're supposed to be proving that $f(n)\geq c\,g(n)$ is true for all large enough $n$: in other words, you need to prove that "$n$ is big" implies the inequality. What you've done is shown that, if the inequality holds, then $n$ must be big. But that doesn't prove that the inequality holds for all $n$: it just proves that any values of $n$ for which the inequality holds must be at least $34$.

David Richerby
  • 2,450
  • Actually that's exactly what he said. Also, what would be the correct way to prove it? I've really searched a lot, but still can't quite understand it fully. I want to show the correct proof to the teacher. – andre_ss6 Aug 30 '16 at 12:40
  • You just need to prove that $n\geq 34$ implies that $n+34\geq cn$, instead of the other way around. – David Richerby Aug 30 '16 at 12:46
  • Ok, so I would, for example, choose $n = 34$ and resolve it until I find $c$? Also, would this work for a case like the one shown in the image? – andre_ss6 Aug 30 '16 at 13:16
  • Choose a value for $c$. Then, start with the hypothesis that $n\geq 34$ and use this to prove that $n+34\geq cn$. – David Richerby Aug 30 '16 at 13:19