How to label a performance profile
Most people call this "cumulative distribution function", or "CDF". A Google image search for "cdf performance" produces many plots of this type with the vertical axes labeled "CDF", which should be understood by people in the field if the field is "mathematically inclined" enough.

A more verbose way for more divulgative works is to label the horizontal axis


Ratio to best performance, r


and the vertical axis 


Probability of achieving a (performance) ratio &lt; r.


An additional difficulty of your example is that the measure "ratio to best performance" is not easy to explain in very few words. In such cases, a good idea is to use the caption of the figure to further clarify what the axis labels mean. This way, those who do not understand the labels can quickly get more information from the caption.