IITM november 2016

Question

What is the time complexity of finding the kth smallest element in an array?

• A. $O(\log n)$
• B. $o(\log n)$
• C. $\Omega(n\log n)$
• D. $O(n)$

Comments

Build min heap and then check for that element in k levels only. So, it's $O(n) + O(1) = O(n)$

Another ways can be be simple linear search and make an another array of size k that marks the least k elements. Again $O(n)$

---

@abcd2 for what O(1)  ??

---

@saurabh  https://gateoverflow.in/1110/gate2003-23

Answer 1

Build Min heap O(n)

Delete min elements upto k times = k * O(log n)

Insert all k elements back k * O(log n)

Dominating term O(n) so (D) is the answer.

Since Omega() will be the lower bound, but here in worst case k = n, so O(n logn) should be given for n logn to be a correct answer.