DBSCAN Time Complexity · Naive O(n²) vs O(n log n) with Spatial Indexing

DBSCAN’s time complexity depends critically on the region query implementation.

Naive Implementation

For each point, check distance to every other point → $O(n^2)$ region queries × $O(d)$ distance computation = $O(n^2 d)$. Practical for n < 10,000 on modern hardware.

Spatial Index Implementation

With a spatial index (R*-tree, kd-tree, ball tree): each region query is $O(\log n)$ on average. Total: $O(n \log n)$ with $O(n)$ for index construction. This is the standard scikit-learn implementation with algorithm='ball_tree'.

Worst Case

In high dimensions, spatial indices degrade to $O(n)$ per query (the index cannot effectively prune the search space). Total: $O(n^2)$ regardless of the index choice. This is fundamental — not an implementation limitation — and explains why DBSCAN should not be used on high-dimensional data without dimensionality reduction.

Memory

$O(n)$ for the spatial index (tree structure) + $O(n)$ for labels and core sample flags. The distance matrix is not stored explicitly (computed on-the-fly), which is the key difference from algorithms that require an $O(n^2)$ matrix.

Practical Runtimes (scikit-learn, single core)

• 10,000: 2 · <1 second
• 50,000: 2 · ~3 seconds
• 100,000: 10 · ~10 seconds
• 500,000: 10 · ~60 seconds
• 1,000,000: 2 · ~3 minutes

HDBSCAN is typically 2–5× slower than DBSCAN for the same dataset size due to the additional hierarchy construction.