
As in BS, WBS recursively identifies the candidate change point estimators
and partitions the data into two,
but the search is performed over the randomly drawn background intervals,
and thus its computational complexity is determined by the choice of \(\mathcal {R}_n\)  as \(O(n \vert \mathcal {R}_n \vert )\) .
In order to ensure that each change point is considered on its own within a large enough interval
for its detection and estimation, WBS requires that a sufficiently large number of
background intervals are drawn;
more precisely, \(\vert \mathcal {R}_n \vert \)  is required to increase as
the minimum distance between the change points, \(\delta _n := \min _{1 \le j \le q_n} \delta _j\) ,
decreases such that \((n/\delta _n)^{-2} \vert \mathcal {R}_n \vert \rightarrow \infty \) .
[1]} refines the theoretical analysis of [2]},
and shows that WBS outperforms BS in terms of
both the separation and the localisation rates.
