We propose a benchmark curve that measures the inherent complexity of a detection problem. The benchmark curve is built using a sequence of simple detection methods based upon random projection. It is parameterized by the area above the receiver-operating characteristic curve of the detection method and its computational cost. It divides the plane into regions that can be used to characterize the computational and structural advantages of a given detection method. Numerical illustrations are provided.