- #1

Korisnik

- 62

- 1

- TL;DR Summary
- easy way to find c and n0 if g(n) known in O(g(n))

Is it

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

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

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