GATE Overflow Test Series | Algorithms | Test 1 | Question: 11

Question

Given an array of $n$ elements, you have to design an algorithm to find the $k$ smallest elements in sorted order. The time complexity of the best such algorithm assuming comparison based sorting will be

• A. $O(k \log n)$
• B. $\Theta(n + k \log k)$
• C. $\Theta(n^2)$
• D. $\Theta (n \log k)$

Comments

cool. thanks.

---

kth smallest element can be found in worst case using partion algorithm [i.e. selection procedure] in O(n^2)

if  we take using selection procedure then after finding kth smallest element then we have to sort k elements

O(n^2 +klogk)

if we use median of 5 algorithm then kth smallest can be found in O(n)

after finding kth smallest using median of 5 algo we sort k elements in klogk time

so total O( n+klogk)

---

I understood given ans but can u verify this approach also valid or not :

1.build heap = o(n)

2. w.c all kth smallest will be at  <= k level and array index 1 to 2^k

if leave remain part of array and only take 1 to 2^k index than it is also min heap which also contain all k smallest elements , now delete k elements from this min heap one by one =o(k*logk)

total= O(n+klogk)   

@Sachin Mittal 1 plz verify this approach alos right or not ?

Answer 1

The best possible algorithm will find the $k^{th}$ smallest element in $O(n)$ time and then move all elements smaller than this to its left - partition part of quick sort which again takes $O(n).$ Finally, these $k$ elements can be sorted in $O(k \log k)$ time.

Comments

The initial part of the algorithm is running Quickselect, which runs in $O(n)$ on average but still has a worst case complexity of $O(n^{2})$.

---

But why do we need to sort at the last, can’t we select elements in sorted order?

See the following algorithm.

array // given array of n elements
k_sorted = [ ]
for 1 = 1 to k: //O(k)
    min = find_min(array) // O(n)
    k_sorted.add(min)
    array.delete(min)

Hence, final Time complexity will be O(kn) ≡ O(n)

---

@KineticKarm, Going by your approach in the worst case it will be O(n^2) when k=n.

But what is mentioned in best answer will still have a worst case time complexity of O(nlogn).

Answer 2

we have to find k smallest elements in sorted order,for that 1^st we’ve to find Kth smallest element.

kth smallest element – https://gateoverflow.in/8243/gate2015-2-45 //    Time complexity = O(N)

Now we’ve to output the k smallest lists in sorted order,so sort those k numbers using klogk and output the list.

So, overall time complexity = O(n + klogk)

Comments

But if you applying kth smallest elements algorithm k time so your overall time complexity is O(kn).

And now to sort k elements it take O(klogk).

So overall time complexity O(kn+klogn).we have to take k into consideration .

---

@gatecse are you unaware of the fact quick partition can take O(N^2) time in worst case.. ?