1
$\begingroup$

I ran into the following notation issue:

Suppose that I have two functions $f$ and $g$ and I know that $\displaystyle \lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = c$ for some $1 < c < \infty$.

I want to express that $f$ is an asymptotic upper bound for $g$, but saying $g(n) = O(f(n))$ is worthless because coefficients are dropped.

Is there a way to express this upper bound more tersely than the limit expression above? In other words is there any "order-O-like" notation for expressing this?

Clarification: I'm not looking for any of the symbols here. The question may be too pedantic.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I know that in number theory we usually say that $f(n) << g(n)$ (call it "$f$ is less-than-less-than $g$") when $f$ is asymptotic to $g$ multiplied by some undetermined positive constant, but I don't know if this is what you're looking for. (Here $f$ and $g$ are positive functions of reals) $\endgroup$ – Patrick Da Silva Feb 2 '12 at 9:52
  • 1
    $\begingroup$ It is not clear what you want, since $f(n)\sim cg(n)$ for some $c>1$ is precisely equivalent to the given limit. What additional information do you intend is an asymptotic upper bound to convey? $\endgroup$ – Brian M. Scott Feb 2 '12 at 16:20
  • $\begingroup$ @Patrick Da Silva: that's exactly what I meant; I haven't seen that before. $\endgroup$ – Huck Bennett Feb 2 '12 at 18:03
  • $\begingroup$ @Brian Scott: It's just a question of notation. The point is "$f(n) << g(n)$" is more concise than "$f(n) \sim cg(n)$ for some $c > 1$"; in particular it doesn't introduce another variable to describe the relationship between $f$ and $g$. $\endgroup$ – Huck Bennett Feb 2 '12 at 18:06
  • 2
    $\begingroup$ A widely understood notation seems distinctly preferable to a very slightly more concise notation that needs to be explained. $\endgroup$ – Brian M. Scott Feb 2 '12 at 18:14
1
$\begingroup$

I know that in number theory we usually say that $f(n) \ll g(n)$ (call it "$f$ is less-than-less-than $g$") when $f$ is asymptotic to $g$ multiplied by some undetermined positive constant, but I don't know if this is what you're looking for. (Here $f$ and $g$ are positive functions of reals)

Hope that helps,

Improve this answer
$\endgroup$

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.