2
$\begingroup$

I am writing my first paper, and one of the results can be written as follows:

For any $W,\epsilon$ such that $\epsilon = o\left(\frac{\log^4 W}{W\log\log W}\right)$ and $\epsilon=\omega\left(\frac{\log\log W}{W}\right)$, we obtain a $o(\min \{W, \frac{1}{\epsilon}{\log^2 W}\})$ space algorithm, improving the state of the art.

Is there some standard notation, say $\Gamma$, so I could write:

For any $W$ and $\epsilon=\Gamma\left(\frac{\log\log W}{W}, \frac{\log^4 W}{W\log\log W}\right)$, ...

?

Will appreciate any help !

Improve this question
$\endgroup$
1
  • $\begingroup$ Welcome to SE Computer Science. You cold have slightly extended your question by asking for notational suggestions similar to those used in comparable situations. But it requires some skill writing it all as a single question, as required by the site. $\endgroup$
    – babou
    Commented Jun 28, 2015 at 7:54

3 Answers 3

Reset to default
3
$\begingroup$

I'm also not aware of any specific notation for the concept you want. In the example theorem statement in the question, there's nothing wrong with what you already have ("$\epsilon$ such that $\epsilon=o(\cdots)$ and $\epsilon=\omega(\cdots)$"). In other situations, it might be more convenient to say something like, "For any $\epsilon\in o(\cdots)\cap\omega(\cdots)$".

Improve this answer
$\endgroup$
3
$\begingroup$

I have seen a "$o$-relation" (asymptotic dominance), namely

$\qquad\displaystyle f \prec g \iff f \in o(g)$.

This allows you to write

$\qquad\displaystyle \frac{\log\log W}{W} \prec \epsilon \prec \frac{\log^4 W}{W\log\log W}$,

which reads more in line with $\leq$-bounds while denoting the asymptotic flavor of the bound.

Note that $\epsilon$ is usually used for constants while you use it as a function in the input $W$. This may be confusing for some readers, at least if it is not standard in your particular subfield.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You can also use $\ll$. In any case, don't forget to define this notation, since it is non-standard in our field. $\endgroup$
    – Yuval Filmus
    Commented Jun 29, 2015 at 5:45
  • $\begingroup$ I find $\ll$ confusing since it is used as "a lot smaller" (without the asymptotic flavor). But yes, pick whichever symbol you like (I'd probably go with $\leq_O$, $\geq_{\Omega}$, $=_{\Theta}$, $>_{\omega}$ and $<_o$) and define it. $\endgroup$
    – Raphael
    Commented Jun 29, 2015 at 8:22
2
$\begingroup$

No, I'm not familiar with any such notation. I suggest you stick with what you have: it should be understandable to your audience. And isn't that what we care most about -- communicating clearly?

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks for the answer. Since I compare my technique to two known algorithms, all of my results discuss certain asymptotic range. I have multiple theorems/lemmas using this form and thought of adding to the preliminaries an explanation for the notation. The question was whether it appears in the literature or I should make up one (I like the use of $\Gamma$ for some reason, but perhaps $\gamma$ is more appropriate as the asymptotic is strict). $\endgroup$
    – Arti C
    Commented Jun 28, 2015 at 7:10
  • $\begingroup$ @ArtiC Given your purpose, I would avoid the notation you suggest, which looks too much like a fuction call, thus interpretable as function composition.. I think the concept you are after is that of a range in some ordered structure. So I would rather use a notation with special parentheses, looking like square brackets, or maybe even just square brackets ... after defining the notation, of course. AFAIK, the use of square brackets for the concept of a range would not have another common standard meaning when applied to functions. $\endgroup$
    – babou
    Commented Jun 28, 2015 at 7:47
  • $\begingroup$ @ArtiC Rather than $\epsilon=\Gamma\left(\frac{\log\log W}{W}, \frac{\log^4 W}{W\log\log W}\right)$ I would suggest something like $\epsilon\in\left[\!\left(\frac{\log\log W}{W}, \frac{\log^4 W}{W\log\log W}\right)\!\right]$ with a $\in$ sign rather than an $=$ sign. The double parentheses are produced by $\left[\!\left(xxx,yyy\right)\!\right]$ giving $\left[\!\left(xxx,yyy\right)\!\right]$. But I also suggest avoiding new notation unless you have a significant use for it. $\endgroup$
    – babou
    Commented Jun 28, 2015 at 8:18
  • $\begingroup$ @babou Just from the point of view of LaTeX, \left[\!\left( will produce unreliable results because the spacing of the two brackets depends on their size, so \! may fail to "undo" that spacing correctly. And, on my screen at least, it fails in your first example, which just looks like $[(\cdots)]$. $\endgroup$
    – David Richerby
    Commented Jun 28, 2015 at 8:25
  • $\begingroup$ @DavidRicherby I am aware of the difficulty. This was meant as an example. Besides, it can be handled on an ad hoc basic, or it can probably be done with a proper macro, that will reduce spacing according to size. I am sure it can be achieved with TeX, probably LaTeX too, though not necessarily easy. But there is a site to ask for that. It is very possible that the proper TeX construct would not work on SE with MathJax. $\endgroup$
    – babou
    Commented Jun 28, 2015 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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