2 ms·

So they took n^(1/2) out of the gate complexity and put it into the time complexity. An interesting trade.