# Providing Tight Example in Approximation Algorithm Analysis

Let's say I found a 2-approximation algorithm for a certain problem and I want to show that the analysis is tight.

Do I now need to come up with an example of generic size $n$ or does it suffice to show that I have an example of size $10$ for which the algorithm yields $2OPT$?

Sometimes, however, you prove something like $ALG \leq 2OPT + 1$. This means that your approximation ratio is really $2 + o(1)$. To show that this is tight, you will need an example for infinitely many sizes (but not necessarily for a generic size; perhaps all your examples have even size).
If your algorithm achieves a 1.5 approximation on all but a finite set $S$ of instances, on which your algorithm achieves a 2-approximation, then you could "improve" your algorithm by "hardwiring" the optimal solutions for the instances in $S$ into your algorithm. In short, for theoretical purposes, an algorithm that succeeds on all but a finite set of instances is just as good as an algorithm that always succeeds. Therefore, a theoretically meaningful tight example is actually an infinite family of tight examples. As Yuval says, any infinite family of examples will do, you don't need an example for every instance size.
• @user695652 "finite" $S$ means that $|S| = O(1)$. you can choose which case to apply in $O(1)$ time. of course that might be a HUGE constant -- but that's the nature of asymptotic analysis. – Sasho Nikolov Oct 18 '12 at 22:11