3
$\begingroup$

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.)

$\endgroup$
1
$\begingroup$

The tilde usually suppresses logarithmic factors. So in your case, the true upper bound should be something like $$ O\left(\frac{n}{A^3 \epsilon} \bigl(\log n \log A \log \frac{1}{\epsilon}\bigr)^{O(1)} \right). $$ (Equivalently, you can replace $\log n \log A \log \frac{1}{\epsilon}$ with $\log n + \log A + \log \frac{1}{\epsilon}$, or equivalently, with $\log \frac{nA}{\epsilon}$.)

You're right that $\tilde{O}$ notation is ambiguous, but in most cases the intended meaning is apparent.

$\endgroup$
  • $\begingroup$ I don't think this answers the question. The problem is not the tilde. I know what it means. Or I thought I did. Your definition is different from the one I tried to use. (Is there a reference for this definition of $\tilde{O}$-notation? I've never seen it.) Regardless, neither definition works. You can still choose ($n$, $A$, $\epsilon$) so as to make $A$ arbitrarily large while keeping the expression inside the asymptotic notation constant. $\endgroup$ – user12186 Jul 10 '18 at 8:55
  • 2
    $\begingroup$ Your assumption that there is a formal definition that matches all use cases is just not true. The $\tilde{O}$ notation is somewhat informal. When the meaning isn’t immediately clear, the authors should include a more accurate statement somewhere. The main goal of using $\tilde{O}$ notation is reduce clutter at the expense of a small loss of accuracy. Therefore we do not care as much about formalities, and do not avoid ambiguity at all cost. $\endgroup$ – Yuval Filmus Jul 10 '18 at 8:58
  • 1
    $\begingroup$ For example, it may be the case that the stated running time is only valid under a certain constraint relating $n$ and $A$. This should be explained in the formal formulation of the result, but can be suppressed in the introduction. $\endgroup$ – Yuval Filmus Jul 10 '18 at 9:00
  • 2
    $\begingroup$ The proof of Lemma 6 in the paper you cite contains an $O$ bound with all error terms. Presumably, if you read the entire section then you also discover some restrictions on the value of $A$ (choosing $A$ too large compared to $n$ doesn’t make sense, one could guess). $\endgroup$ – Yuval Filmus Jul 10 '18 at 9:04
  • $\begingroup$ "For example, it may be the case that the stated running time is only valid under a certain constraint " - Thank you, I hadn't considered this. $\endgroup$ – user12186 Jul 11 '18 at 8:53

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.