# Term for an approximation that becomes better as the problem grows

For a certain maximization problem, a "constant-factor approximation algorithm" is an algorithm that returns a solution with value at least $F\cdot \textrm{Max}$, where $F<1$ is some constant and $\textrm{Max}$ is the exact maximal value.

What term describes an algorithm in which the approximation factor is a function $F(n)$ of the problem size, and $F(n)\to 1$ as $n\to \infty$?

• Is approximation factor even the right notion in such circumstances. For example, a constant additive error has the property that, as $\mathrm{OPT}\to\infty$, $(\mathrm{OPT}+\mathrm{err})/\mathrm{OPT}\to 1$. – David Richerby Nov 8 '15 at 15:00

You can say your algorithm is asymptotically optimal. One example is universal codes, which are a certain type of codes for the natural numbers. They satisfy the following property. Let $D$ be a monotone probability distribution over the natural numbers, that is $\Pr[D=n] > \Pr[D=n+1]$. The average codeword length under a universal code is $H(D)(1 + o(1))$. Since $H(D)$ is the optimal length, universal codes are asymptotically optimal, in exactly the same sense as the one you're after.