Korisnik
- 62
- 1
- TL;DR
- 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)##.
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)##.