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.

  • 1
    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)2012-02-02
  • 1
    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?2012-02-02
  • 0
    @Patrick Da Silva: that's exactly what I meant; I haven't seen that before.2012-02-02
  • 0
    @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$.2012-02-02
  • 2
    A widely understood notation seems distinctly preferable to a very slightly more concise notation that needs to be explained.2012-02-02
  • 0
    Sigh. Fair enough.2012-02-02
  • 0
    @Brian : In the number theory contexts where I've seen this notation appear, it is very widely understood ; they were analytic number theorists and use this all the time.2012-02-02

1 Answers 1

1

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,