Can an algorithm run in "O(n/a)" time? 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 &gt; 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 &gt; 0$, we can find an $a_\epsilon \geq a_0$ such that 
$C \cdot n_0/a_\epsilon &lt; \epsilon$, and thus $f(n_0, a_\epsilon) &lt; \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.
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&nbsp;$\epsilon$ correspond to better approximations. As such, a running time that's polynomial in $n$ and&nbsp;$1/\epsilon$ is what you'd intuitively look for: it's saying that a better approximation (smaller&nbsp;$\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&nbsp;$\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&nbsp;$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}$.