0
$\begingroup$

(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?

$\endgroup$
1
  • $\begingroup$ You're looking for "big Theta" notation. $\endgroup$ – Antonio Vargas Sep 25 '18 at 9:43
0
$\begingroup$

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.

$\endgroup$
2
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.