0 votes 0 votes Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$.What about a fraction of $1/n$ inputs of length $n$? What about a fraction $1/2^n$? Algorithms cormen algorithms sorting descriptive + – akash.dinkar12 asked Jun 28, 2019 akash.dinkar12 265 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.