Linearithmic

Quasilinear time

An algorithm is said to run in quasilinear time (also referred to as log-linear time) if ${\displaystyle T(n)=O(n\log ^{k}n)}$ for some positive constant ${\displaystyle k}$; linearithmic time is the case ${\displaystyle k=1}$. Using soft O notation these algorithms are ${\displaystyle {\tilde {O}}(n)}$. Quasilinear time algorithms are also ${\displaystyle O(n^{1+\varepsilon })}$ for every constant ${\displaystyle \varepsilon >0}$ and thus run faster than any polynomial time algorithm whose time bound includes a term ${\displaystyle n^{c}}$ for any ${\displaystyle c>1}$.