The size p^* of the region of attraction of the global minimum in relation to A.

The region of attraction of a local minimizer S(x_m) is defined as the largest region containing x_m, such that when starting an infinitely small step strictly descending local minimization from any point in S(x_m), then the minimizer x_m will be found each time. The region of attraction of of a minimum m is the union of regions of attraction of all minimizers x for which f(x) = m.

If the region of attraction of f^* is large then this region is easy to detect when sampling in A and such a problem is of course easier to solve than a problem with smaller such region.

The affordable number of function evaluations N_f

The value of the expression (1-p^*)^N_f is the chance to miss the region of attraction of f^* when sampling N_f points at random in A. If the function f is cheap to evaluate then N_f is large and and the probability that even a very small region of attraction is missed becomes small. However, if only a small number of function evaluations can be performed then the probability to miss the region of attraction of the global minimum even for large p^* is large.