Oh I wasn't claiming it's O(n), just O(n^{1+epsilon}) for any epsilon > 0. Indeed, the function inside your O is dominated by n^{2 + epsilon} for any epsilon > 0.