# Finite Sample Complexity Analysis of Binary Segmentation

arXiv: https://arxiv.org/abs/2410.08654 · HTML: https://mlsanity.com/paper/2410.08654/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 25 references that are in the map.
- First posted on arXiv 11 Oct 2024.

## Builds on (most cited first, 5 of 5)

- [On Optimal Multiple Changepoint Algorithms for Large Data](https://mlsanity.com/paper/1409.1842/) (2014)
- [Narrowest-Over-Threshold Detection of Multiple Change-points and Change-point-like Features](https://mlsanity.com/paper/1609.00293/) (2016)
- [Seeded Binary Segmentation: A general methodology for fast and optimal change point detection](https://mlsanity.com/paper/2002.06633/) (2020)
- [Maximum Margin Interval Trees](https://mlsanity.com/paper/1710.04234/) (2017)
- [Fast Nonconvex Deconvolution of Calcium Imaging Data](https://mlsanity.com/paper/1802.07380/) (2018)

## Abstract (arXiv)

Binary segmentation is the classic greedy algorithm which recursively splits a sequential data set by optimizing some loss or likelihood function. Binary segmentation is widely used for changepoint detection in data sets measured over space or time, and as a sub-routine for decision tree learning. In theory it should be extremely fast for N data and K splits, O(N K) in the worst case, and O(N log K) in the best case. In this paper we describe new methods for analyzing the time and space complexity of binary segmentation for a given finite N, K, and minimum segment length parameter. First, we describe algorithms that can be used to compute the best and worst case number of splits the algorithm must consider. Second, we describe synthetic data that achieve the best and worst case and which can be used to test for correct implementation of the algorithm. Finally, we provide an empirical analysis of real data which suggests that binary segmentation is often close to optimal speed in practice.