Breaking the O(N²) ceiling