It is not
O
(
n
log
n
).