Can an algorithm run in "O(n/a)" time?

Question

On one hand, it seems to make no sense, because of the following:

When expanded, the claim $f(n,a) \in O(n/a)$ would be

There exist $C > 0$, $n_0$, and $a_0$ such that if $n \geq n_0$ and $a \geq a_0$, then $f(n,a) \leq C \cdot n/a$.

Now, given any $\epsilon > 0$, we can find an $a_\epsilon \geq a_0$ such that $C \cdot n_0/a_\epsilon < \epsilon$, and thus $f(n_0, a_\epsilon) < \epsilon$.

So for any $\epsilon$, there is an input, with $n = n_0$ and $a = a_\epsilon$, at which the algorithm takes less than $\epsilon$ time to run. But any nontrivial algorithm performs at least one operation, regardless of the input. So this seems nonsensical.

On the other hand, you can imagine someone saying that some approximation algorithm runs in time "$O(n/a)$", where $n$ is the size of the input and $a$ is the maximum multiplicative error.

And in fact, there is a paper in which an algorithm is claimed to run in "$\tilde{O}(\frac{n}{A^3 \epsilon})$" time. (Yes, I know $\tilde{O}$ is different from $O$). I asked a longer question about that here. This question is an attempt to isolate the core confusion there.

Answer 1

For approximation algorithms, the algorithm must return an answer within a factor of $1\pm\epsilon$ of the true value. As such, smaller values of $\epsilon$ correspond to better approximations. As such, a running time that's polynomial in $n$ and $1/\epsilon$ is what you'd intuitively look for: it's saying that a better approximation (smaller $\epsilon$, so larger $1/\epsilon$) will take more time, but not by an unerasonable amount.

Also, note that we typically have an upper bound on $\epsilon$. For example, suppose we want to approximately compute the distance between two distinct vertices in a connected graph. We know the distance must be between $1$ and $n$ the number of vertices) so if we just want an approximation within $1\pm\epsilon$ and $\epsilon\ge\sqrt{n}$, we can just return $\sqrt{n}$.

Answer 2

The interpretation is closer to the following:

There exists $C>0$ such that for all $n,a$, $f(n,a) \leq C(n/a)$.

But this is also not quite right, since not all values of $n,a$ make sense.

Taking a look at the actual paper, we see that Algorithm IV calls Algorithm V with the parameter $B = A/2\sqrt{\log(2/A\epsilon)}$.

Algorithm V, in turn, tacitly assumes that $B^2 \leq n$ (note that confusingly enough, they use $A$ instead of $B$ for the approximation parameter). This means that $A$ is constrained to satisfy $$ \frac{A}{2\sqrt{\log(2/A\epsilon)}} \leq \sqrt{n}. $$

The running time of Algorithm IV is stated in full in Lemma 6: $$ O\left(\frac{n}{A^3 \epsilon} \log^2 \frac{1}{A\epsilon}\right). $$ This means that there exists a constant $C$ such that the running time is at most $$ C\frac{n}{A^3 \epsilon} \log^2 \frac{1}{A\epsilon}, $$ for all $A,\epsilon,n$ satisfying $$ \frac{A}{2\sqrt{\log(2/A\epsilon)}} \leq \sqrt{n}. $$ (There might be additional constraints that I missed.)

This is the meaning of $\tilde{O}(\frac{n}{A^3\epsilon})$ for Algorithm IV.