Say we have an algorithm that takes an input a triple ($X$, $A$, $\epsilon$), where $X$ is a sequence of $n$ bytes, of which the algorithm might query only a subset, and $A$ and $\epsilon$ are numbers with $A \geq 1$ and $\epsilon > 0$. It is claimed that this algorithm runs in time
$$ \tilde{O}(\frac{n}{A^3 \epsilon}) $$
as $n \to \infty$, $A \to \infty$ and $\epsilon \to 0$.
(Note that $\tilde{O}$ means big-O except ignoring logarithmic factors. For functions of one variable, $f(n) \in \tilde{O}(g(n))$ iff there exists a $k \geq 1$ such that $f(n) \in O(g(n) \cdot \log^k g(n)$.)
My question is, what exactly does this mean formally?
So this is another question about "asymptotic notation with multiple variables". There are existing questions about this, but they don't apply to this case.
This case is different because the expression $\frac{n}{A^3 \epsilon}$ is decreasing in one of its arguments, namely $A$. The standard definition for asymptotic notation with multiple variables given in Wikipedia breaks down in this case, as described below.
I also tried some "obvious" alternative definitions, which also seem fail, as described below.
(The actual algorithm that I'm wondering about is Algorithm IV in this paper. It's an approximation algorithm that outputs an estimate of $f(X)$ for a certain function $f$, and is claimed to "run in time $\tilde{O}(\frac{n}{A^3 \epsilon})$". From context one can infer that this asymptotic claim is supposed to be true as $n \to \infty$, $A \to \infty$, and $\epsilon \to 0$. (Instead of, say, when $n \to \infty$, $A \to \infty$ and $\epsilon \to \infty$). $A$ and $\epsilon$ determine the error bounds. The larger $A$ and $\epsilon$ are, the looser the bounds are, and the farther the output is allowed to diverge from $f(X)$.)
So, let $F(n,A,\epsilon)$ be the number of operations performed by the algorithm when run with an input of size $n$ and parameters $A$ and $\epsilon$. (If different inputs of size $n$ perform different numbers of operations, let $F(n, A, \epsilon)$ be the maximum.) The claim, whose formal meaning is still unclear, is now
$$F(n, A, \epsilon) \in \tilde{O}(\frac{n}{A^3 \epsilon}).$$
If we unpack the $\tilde{O}$-notation, the unclear claim is that there exists some $k \geq 1$ such that
$$F(n, A, \epsilon) \in O(\frac{n}{A^3 \epsilon} \log^k \frac{n}{A^3 \epsilon}).$$
Failure of the standard / Wikipedia definition
Take this definition and adapt it in an obvious way for the situation where one of the variables approaches $0$ instead of $\infty$, and where we are using $\tilde{O}$ instead of $O$. We get this:
There exist $C > 0$, $M$, and $k \geq 1$ such that if at least one of $n \geq M$, $A \geq M$ and $\frac{1}{\epsilon} \geq M$ holds, then $$| F(n, A, \epsilon) | \leq C | \frac{n}{A^3 \epsilon} \log^k \frac{n}{A^3 \epsilon} |.$$
This fails because we can choose $(n, A, \epsilon)$ so as to make $A$ arbitrarily large while the right-hand side remains constant. That is, for an arbitrarily large $N$, set $n = N^3$, $A = N$, and $\epsilon = \frac{1}{7}$. Regardless of $N$, the right-hand side is $C |7 \log^k 7|$.
But as $N \to \infty$, $F(N^3, N, \frac{1}{7})$ must grow without bound (not necessarily monotonically). This is because, for example, it takes the algorithm $O(\log N)$ operations just to read the bits of the binary representation of the second argument. So for large enough $N$, the left-hand side is larger than the right-hand side, violating the inequality. So the claim doesn't hold.
Adapting the definition from this answer , we would get this claim:
There exist $C > 0$, $n_0, A_0, \epsilon_0$ and $k \geq 1$ such that if all of $n \geq n_0$, $A \geq A_0$ and $0 < \epsilon \leq \epsilon_0$ hold, then $$| F(n, A, \epsilon) | \leq C | \frac{n}{A^3 \epsilon} \log^k \frac{n}{A^3 \epsilon} |.$$
This doesn't work for the same reason as the previous claim. We can make $A$ arbitrarily large while keeping the right-hand side constant.
I have seen the article "On Asymptotic Notation with Multiple Variables". It doesn't seem relevant, because it doesn't deal with the case where the function inside the asymptotic notation is decreasing in one of its arguments.
It makes sense that, when dealing with approximation algorithms, it would be useful to make claims like "this algorithm runs in time $\tilde{O}({\frac{n}{A^3 \epsilon}}$)". In particular, it seems there should already be a standard definition in the field of approximation algorithms for $O$/$\tilde{O}$ notation with multiple variables when the function is decreasing in one of its arguments. But I could not find such a definition. I looked at several articles about classifying the asymptotic complexity of approximation algorithms, but did not find anything that seemed relevant. In particular, the concepts of "polynomial-time approximation scheme" and "fully polynomial-time approximation scheme" seem to be irrelevant here.
Appendix: attempted alternative definitions
I thought this definition might work:
Let $f_A(n)$ be an increasing function and $f_\epsilon(n)$ be a decreasing function such that $f_A(n) \to \infty$ and $f_\epsilon(n) \to 0$ as $n \to \infty$. The following holds: $$(n \mapsto F(n, f_A(n), f_\epsilon(n))) \in \tilde{O}((n \mapsto \frac{n}{f_A(n)^3 f_\epsilon(n)} )). $$
(So this is a claim about the asymptotic behavior of a function of one argument.)
But it also fails. You can define $f_A$ and $f_\epsilon$ so that $\frac{n}{f_A(n)^3 f_\epsilon(n)}$ remains constant as $n \to \infty$; meanwhile $F(n, f_A(n), f_\epsilon(n))$ must grow without bound, even if slowly and non-monotonically, as $n \to \infty$, making the claim false.
You could add the requirement that $f_A$ and $f_\epsilon$ be chosen so that $\frac{n}{f_A(n)^3 f_\epsilon(n)} \to \infty$ as $n \to \infty$. That doesn't help. $f_A$ and $f_\epsilon$ can be chosen so that $\frac{n}{f_A(n)^3 f_\epsilon(n)}$ grows very slowly compared to $f_A(n)$, causing $F(n, f_A(n), f_\epsilon(n))$ to grow faster than $\frac{n}{f_A(n)^3 f_\epsilon(n)}$.
(I'm now thinking that maybe one should add some requirement that $f_A$ and $f_\epsilon$ be chosen so that $\frac{n}{f_A(n)^3 f_\epsilon(n)}$ grows "sufficiently fast". But this seems like it would be rather elaborate.)
