(In combinatorics) When talking about asymptotic behaviour of a function. Seemingly we have already decided the multiplier. For example, we would say $\binom{n}{2}$ is asymptotically $1/2*n^2$, but not $n^2$. My question is, what should we say about a function $f$ if we only know $\lim \frac{f}{n^2}$ is bounded away from $0$ and $\infty$, but don't know that exact number?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ You're looking for "big Theta" notation. $\endgroup$ – Antonio Vargas Sep 25 '18 at 9:43
Add a comment
|
$\begingroup$
$\endgroup$
2
Perhaps the big O notation is what you are looking for?
It's a notation that "ignores the constant factor". By definition, $f\in O(g)$ if there exists some constant $C$ such that $f(x)<C\cdot g(x)$ for all large enough values of $x$. For example, $$an^2+bn+c\in O(n^2)$$ no matter what the particular constants $a,b,c$ are.
-
$\begingroup$ I'm looking for something that can replace "we don't know its asymptotics", Thanks anyway. $\endgroup$ – Peter Wu Sep 25 '18 at 8:43
-
$\begingroup$ @PeterWu If you don't know its asymptotics, you don't know it, there's nothing more to say. I don't see a reason to give that a name. $\endgroup$ – 5xum Sep 25 '18 at 8:49
