a) What is the definition of completeness?
Completeness is the number of objects in a data set that are detected over the number that exist. In astronomy, completeness is often estimated for a particular apparent magnitude or flux density. As an example, for sources that are as bright as the Sun (-27 magnitude), we have a completeness of 1. That is, we’ve discovered all sources in the celestial sphere with the Sun’s magnitude. As we get down to very dim objects like tiny pieces of space junk in Earth orbits, our completeness ratio drops dramatically.
b) How do you calculate the completeness of an observation?
On a ROC curve, completeness is the True Positive Rate or the y-axis if all the objects have been observed (thanks @ProfRob!). If only a fraction of the objects have been observed, completeness is that fraction times the true positive rate. Note that a classifier only yields better completeness at the cost of higher false positive rates. Here is an excellent example of ROC curves for different algorithms which differentiate quasars from stars:
The left panel shows data used in color-based photometric
classification of stars and quasars. Stars are indicated by gray
points, while quasars are indicated by black points. The right panel
shows ROC curves for quasar identification based on u - g , g - r , r - i
, and i - z colors.

If you don’t know the true positive rate, you may be able to run a simulation in which you inject objects into your data set and determine what portion of these are found by your algorithm. This will give you an estimate of your completeness. Matlab has a specific function for ROC curve Monte Carlo simulation, for example.