The problem of determining whether a program has 'optimality performance' A or 'optimality performance' B for just about any definition of 'optimality performance' is undecidable in general (proof below). This implies that there is no single method that can always tell you how optimal an algorithm is.
There are however methods that are often applied when analyzing approximation algorithms. Often, approximation algorithms are evaluated by their guarantees on how far its solution is from the optimal solution. I'll give an example problem and approximation, which I will prove using the 'lower bound' method, which is a very commonly used method to prove ratios.
The problem in question is the 'Truck Loading' problem: we have a lot of identical trucks (as many as we like), each capable of carrying a load weighing at most T. We have n objects we wish to load in these trucks for transport. Every object i has a weight w_i, where w_i <= T (so there are no items that can't fit on a truck even by themselves). Items cannot be divided into parts. We'd like to fill up trucks so that we need as few trucks as possible. This problem is NP-complete.
There is a very easy approximation algorithm for this problem. We simply start loading a truck with items, until the truck is so full that the next item won't fit. We then take another truck and load this truck with this item that didn't fit on the previous truck. We don't load any more items on this truck: instead, we take a new truck, we fill it with lots of items again until it no longer fits, put that last item on its own truck again and so forth.
This algorithm is a so-called 2-approximation for the problem: it uses at most twice as many trucks as the optimal solution would need. The 'at most' is crucial: we might be lucky and find the optimal solution, but at least we won't do too bad.
To prove this, we first define a lower bound on the optimal number of trucks we need. For this, imagine that we are allowed to cut items into parts: we could then easily fill every truck but the last one completely. The number of trucks we'd need if we did that is a lower bound for the number of trucks we need for the original question: in the 'best' case the optimal solution always fills every truck completely, in which case the number of trucks is equal, but if the optimal solutions leaves trucks unfilled, then it can only need more trucks.
Now we look at our approximation algorithm. Note that in every step, we (partially) fill up two trucks. Also note that by how the algorithm works, the items in the first truck and the item in the second truck together cannot fit in the first truck, so their sum is at least T. This means that every step, we load at least a full truck worth of items on two trucks. Now compare this to our lower bound: in that case, we load a full truck worth of items on one truck. In other words, our approximation algorithm computes (in linear time) a solution that looks very much like our lower bound 'solution', but uses two trucks instead of one. Hence, we use at most twice as many trucks as the optimal algorithm, because we use at most twice as many trucks as our lower bound on the optimal algorithm.
This algorithm gives a constant-factor approximation: it is at most 2 times as bad as the optimal solution. Some examples of other measures: at most C more than the optimal solution (additive error, quite uncommon), at most c log n times as bad as the optimal solution, at most c n times as bad as the optimal solution, at most c 2 ^ (d n) times as bad as the optimal solution (very bad; for instance, general TSP only admits algorithms with this kind of guarantees).
Of course, if you want to be sure that the factor you prove is the best factor you can prove, you should try to find instances in which the solution your algorithm gives is indeed as bad as it possibly can be.
Also note that we sometimes use approximation algorithms on problems that are not NP-hard.
I learned this (among a lot more) in the approximation algorithms course at my university.
Undecidability proof: let P be a problem and A and B be approximation algorithms for P where A and B do not have the same 'optimality' for some sensible definition of 'optimality', and where the running time of A and B is both omega(1) (strictly slower than constant time, ie, they become slower for larger instances) and where A and B both always halt.
Let D be a program that claims that it can compute the following: given some program C computing an approximation for P, decide whether it is as good as A or as good as B for sufficiently large inputs (you can therefore use this to categorize programs according to their optimality).
We can then use D to solve the halting problem. Let E be a program and F be an input for this program. We will use D to decide whether E will halt on input F.
We design a program G that does the following: given an input S for problem P, it runs E on F and A on S in parallel: it executes E for a while, then A, then E again and so forth. If E halts on F, it stops running A and instead runs B on S and returns B's result. If A halts before E halts, it returns A's result.
Using D on G now decides whether E halts on F: if E halts on F, then for sufficiently large inputs S, E halts on F before A halts on S (because the time it takes E to halt does not depend on the size of the input, unlike A). D therefore reports that G has the optimality characteristics of B. If E doesn't halt on F, D will report that G has the optimality characteristics of A.