Superlinear can mean O(n log n) or anything like that, which is smaller than O(n^2).