Everything That Fits

The constraint line says $n \le 2 \cdot 10^5$ and the limit is one second. Take the USACO Guide's conservative figure of $10^8$ elementary operations per second.

candidate	operation count at $n = 2 \cdot 10^5$
$O(n^2)$	?
$O(n \sqrt n)$	?
$O(n \log n)$	?
$O(n \log^2 n)$	?
$O(n \sqrt n \log n)$	?

Select every complexity that fits inside the $10^8$ budget.

$O(n \sqrt n)$ , about $8.9 \cdot 10^7$

$O(n \sqrt n \log n)$ , about $1.6 \cdot 10^9$

$O(n \log n)$ , about $3.5 \cdot 10^6$

$O(n \log^2 n)$ , about $6.2 \cdot 10^7$

$O(n^2)$ , about $4 \cdot 10^{10}$