Question

We can find and sort the k largest elements of a set of size n in Θ(n + k log k) worst-case time.

Is this statement true?

Answer 1

Hello Reader,

Making the long story short, Yes We can find and sort the k largest element of a set of n elements in Θ(n+k log k) time.

To be more precise the exact time would be something: Θ( (n-k)*k + k log k )

1.) The time required to find the k largest element would be K*(n-K).

2.) The time required to sort the k elements using merge sort would be K log K

Algorithm:

1.) Take the array or set of size n.

2.) Take the elements form 1-k into some temporary array t1, remaining k+1 - n elements into temporary array t2.

3.) Find the minimum element in array t1 and compare it with each element of t2, if min < any element of t2 then swap the elements in both the array.

4.) Again check for the minimum element in t1 and repeat the above step k times.

So the time to find the K largest element is Θ((k-n)*k) or Θ(n).

Then sorting is simple business i.e Apply merge sort which is Θ(n log n) but we apply it in only the array t1 which has k elements so Θ(k log k).

Thus we conclude that Θ(n + k log k ) is possible.

Hope you like the arguments above.

Any suggestion and questions are welcomed in the comment box.

Thanks and regards and keep loving us!!!!!!!!!