Big O: find ##c## and ##n_0## if ##g(n)## is known

[Korisnik]

TL;DR Summary

easy way to find c and n0 if g(n) known in O(g(n))

Is it guaranteed that when I have any kind of function ##f##, that I'll be able to find constants ##c## and ##n_0## if I know ##g## by simply adding up the factors multiplying all the terms in the equation?

Suppose ##f(n) = a\cdot n^{143} + b \cdot n! + d \cdot (n!)! + m \cdot 2^n - p \cdot \sqrt{n} + 42##, now I know here that ##f## is ##\mathcal{O}((n!)!)##, meaning that ##g(n) = (n!)!## (where ##\mathcal{O}## takes ##g(n)##).

But can I immediately assume that that holds if I pick ##c = a + b + d + m + p + 42## (taking absolute values of all the factors multiplying each term in ##f(n)##) and letting ##n_0 = 1## such that ## 0 \leq f(n) \leq c \cdot g(n), \ \forall n\in\mathbb{Z}^+,\ n\geq n_0##?

Will this technique work for all functions ##f##? Moreover, I think this can be simplified further by not even taking the factors before negative terms (in this case ##p##).

Thanks in advance.

Edit:

Actually, I think this is sort of trivial to prove, because if indeed we have the "biggest" function ##g(n)## figured out, then if we simply do the following: $$0 \leq f(n) = a\cdot n^{143} + b \cdot n! + d \cdot (n!)! + m \cdot 2^n - p \cdot \sqrt{n} + 42 \leq c \cdot g(n) = (a + b + d + m + p + 42) \cdot (n!)! = a \cdot (n!)! + b \cdot (n!)! + d \cdot (n!)! + m \cdot (n!)! + p \cdot (n!)! + 42 \cdot (n!)!$$ and each of these new terms grows faster than each of the terms in ##f(n)##, and further, since negative terms only "discontribute", there's no need to even include those, because by excluding them, you get a faster growing function than ##f(n)##.

 

[mfb]

With n₀=1 this won't work.

Consider f(x)=x!+2^x. Your approach would lead to g(x)=2x!, then g(1)=2 but f(1)=3.

The approach works if you choose an n₀ such that the other terms have the asymptotic inequalities, in this case ##x! \geq 2^x##.