Finding n0 in big O notation

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?

Solution

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