If partial sorting is relaxed so that the "k" smallest elements are returned, but not in order, the factor of O("k" log "k") can be eliminated. An additional maximum selection (taking O("k") time) is required, but since formula_1, this still yields asymptotic complexity of O("n"). In fact, partition-based selection algorithms yield both the "k"th smallest element itself and the "k" smallest elements (with other elements not in order). This can be done in O("n") time – average complexity of quickselect, and worst-case complexity of refined partition-based selection algorithms.