Reduction to $n\log n$ time problem If a problem $A$ is poly-time reducible to a problem $B$ ($A &lt;_\mathrm{p} B$), and $B$ can be solved in time $O(n\log n)$, can $A$ also be solved in time $O(n\log n)$?
You can't guarantee that $A$ can also be solved in time $O(n\log n)$ because the reduction from $A$ to $B$ might require more time than that (for example, $n^3$ steps).