1

This is a continuation of my previous question here. I learned how to validate if the relationship holds for 

3n2 − 100n + 6 = O(n2),

because I choose c = 3 and 3n2 > 3n2 − 100n + 6;

specifically if c = 1 and n0 is 0.06, if n is greater than 0.06, say n = 5,

5^2 = 25 > 3*5^2 − (100*5) + 6 = -469

Now, it seems I am unable to apply the same method with the following equation.

3n2 − 100n + 6 = O(n3), because I choose c = 1 and n3 > 3n2 − 100n + 6 when n > 3;

What bothers me is the "when n > 3" part, suppose n = 2

f(n) - 3*2^2 − (100*2) + 6 = -182

f(g) - 2^3 = 8

8 > -182

The relationship still holds!

I think I am making a mistake somewhere because I have not been able to satisfy myself that the relation will only hold when n > 3. What should I do?

Community
  • 1
  • 1
lightning_missile
  • 2,821
  • 5
  • 30
  • 58
  • That is why the definition says `for n>n0`. It doesn't matter if it holds for `n – ndnenkov Dec 22 '15 at 15:35
  • @ndn I think it's no longer 0.06. I understand the problem earlier, but now having trubble with the new one "3n2 − 100n + 6 = O(n3), because I choose c = 1 and n3 > 3n2 − 100n + 6 when n > 3;". I'm bothered with the "when n > 3", because I tried if n = 2 the relation still holds? That is, 8 > -182 (please see at the end of the question). This time the book provides the value of n0, but I can't convince myself that the relation can't be true if n <= n0 (3). – lightning_missile Dec 22 '15 at 15:46
  • sorry, didn't see the new question was about `O(n^3)`. The same logic still applies. – ndnenkov Dec 22 '15 at 15:51
  • @ndn but why n > 3? It's still true if n < 3 E.G. n = 2, right? – lightning_missile Dec 22 '15 at 15:55
  • `n>3` is just an example. You can use any `n0`, as long as the condition holds true. For example `n0 = -100` won't cut it. – ndnenkov Dec 22 '15 at 15:57

1 Answers1

3

As I've written in my answer to your question in the previous thread, the set of constants (c, n0) that fulfils

f(n) < c · g(n), for all n > n0,                         (+)

is not unique. Also, you needn't find the "highest" n>n0 to show asymptotic behaviour, but rather any n0 that shows whatever asymptotic relation you want to prove. Recall that since we're interested in the asymptotic behaviour, we don't really care about how the function (or algorithm) behaves for small values of n (say n=2 or n=3).

Also, Big-O describes an upper bound on the asymptotic behaviour of a function (or algorithm), but it needn't be the best or tightest bound. E.g., 

f(n) = 3n^2 - 100n + 6

    f(n) is in O(n^2) (as shown in previous thread)        (i)
    f(n) is in O(n^3) (as shown in your question here)     (ii)

Here, we can show both (i) and (ii), but the former provides a tighter bound for the asymptotic behaviour of f(n) than the latter. Usually, we want to find an Big-O bound that is as tight as possible, but in practice, sometimes a good enough bound is sufficient. Consider the following situation:

  • Consider we have some function or algorithm f(n). Moreover, say there is a huge effort in showing whether this f(n) is in O(n^2) or not, whereas showing that f(n) is in O(n^3) is readily done in a few minutes. Then say your boss needs to know if your algorithm performs at least "better" than n^3 asymptotically: hence, showing that f(n) is in O(n^3) suffices. Most likely, in this case, your employer would not wish for you to spend the full afternoon showing that f(n) is, in fact, ever "better" than n^2 asymptotically.

At your request I'll add an explanation of how to show that f(n) is in O(n^3), and why the (non-unique) choice of constant c=3 makes sense (= easily obtained)

Problem: Show that f(n) = 3n2 − 100n + 6 is in O(n3)

We'll use an approach similar to the one in the previous thread.

Let's describe your functions as a sum of it's highest term and another function

f(n) = 3n^2 + h(n)                                       (*)
h(n) = 6 - 100n                                          (**)

In the previous thread we showed, quite readily, that (I just list results here)

    => h(n) < 0, given n > 6/100                         (i)
    => f(n) < 3*n^2, given n > 6/100                     (ii)

Now, consider the following function

g(n) = n^3                                               (***)

What can we say about this function in terms of 3*n^2, using also results (i-ii) above?

for n = 3: g(3) = 3^3 = 3*3^2 > f(3) ((ii): since n = 3 > 6/100)
hence,    

   =>  for n > 3: g(n) > f(n)                            (iii)

Now, we reached (iii) quite easily since already had result (ii), which in turn, were also reached quite easily. Hence, the choice of n0=3 comes quite naturally. Also, note that (iii) exactly describes the relation (+), but with constant c=1; hence choosing c as 1.

Hence, we've shown that (+) holds for constant set (c,n0) = (1,3), and subsequently, f(n) is in O(n^3).

Again, we could possibly find a lower value of n0 by directly attacking the problem "for which smallest value of n0 does 'n^2 - 100n + 6 < n^3, n>n0' hold?", but we're not really interested in this: we want to look at the asymptotic behaviour of the function we study.

Hence, any constant set (c,n0) that helps us to show (+) suffices, and any further work in finding other constant sets (with smaller n0 values, and so on) could perhaps be a valuable exercise in algebra, but not of value for our analysis of the asymptotic behaviour of f(n).

Community
  • 1
  • 1
dfrib
  • 70,367
  • 12
  • 127
  • 192
  • what about the way I came up with comparing the two functions? That is, the way I just substituted n like "f(n) - 3*2^2 − (100*2) + 6", how does it compare with the method you described in the previous thread? – lightning_missile Dec 22 '15 at 16:10
  • @morbidCode in the last "code box" in your question above, you are doing a point-comparison between two functions (comparing their values at specific point). This cannot really be used to say anything regarding their asymptotic behaviour, as a point-local investigation says little about a functions behaviour at all. Regarding your second question in the comment above: I'll edit in an example of analysing the function w.r.t. O(n^3). – dfrib Dec 22 '15 at 16:16
  • thanks for this! I would like to know since you already mentioned something about algebra. What algebra skills do I need to solve these kinds of problems? I see you used linear inequalities to find n where equation -100n+6 = 0, is that correct? – lightning_missile Dec 22 '15 at 17:04
  • @morbidCode You're welcome, good luck with your coding and Big-O studies! – dfrib Dec 22 '15 at 17:49
  • thanks. Ah, regarding my big-O studies. I have a follow up question, one that I think will help me decide to continue. Do you mind answering it? http://stackoverflow.com/questions/34421620/role-of-lower-order-terms-in-big-o-notation thanks again! – lightning_missile Dec 22 '15 at 17:52
  • sure, I'll look at it. – dfrib Dec 22 '15 at 18:09