[kripke]

The choice of A_i now depends on n. The complexity of your construction is O(n^{2 + 1/argmax_i { N_i <= n}), not O(n^2).

[woopwoop]

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.