3 ms·
Finding sorted(array)[k] is possible in linear (even worst case!) time. Using that n times would as you note take n^2 time. But we could employ a trick. Once we
by im3w1l 11y ago
Finding sorted(array)[k] is possible in linear (even worst case!) time. Using that n times would as you note take n^2 time. But we could employ a trick. Once we have been asked for log n elements, and have thus already spent n log n time, we could then sort the array.