Quasilinear time

An algorithm is said to run in quasilinear time (also referred to as log-linear time) if for some positive constant ; linearithmic time is the case . Using soft O notation these algorithms are . Quasilinear time algorithms are also for every constant and thus run faster than any polynomial time algorithm whose time bound includes a term for any .

Algorithms which run in quasilinear time include:
* In-place merge sort,

1.Previous
3.Next