Test by Bikram | Algorithms | Test 2 | Question: 24

Question

Given $n$ number of linearly ordered distinct elements, what will be the worst case time complexity to find

$p$-th smallest element $(1 \leq p \leq n)$ from these $n$ elements when $n > 50$?

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

Comments

We can use the max heap of size p.We will scan the elements from left to right.

1) Firstly we will build max heap of first p elements. It just takes O(p) time.

2) Now after that, we will start from (p+1)th element

a)If the root is smaller than the current element we will delete the root and then place the current element at the root. Then we have to call the max heapify.

b)If the root is greater then the current element then we simply move to next element.

Repeat till we hit the right end of the array.

At the end, the heap will contain p smallest elements and whose root will give pth smallest element.

step 1 takes O(p)

step 2 In worst case will take (n-p)*(logp)

Total= O(p) + O((n-p)*logp) In worst case p==n

so we get O(n)

---

Can you please make it a bit more clearer?

Answer 1

Build a min - heap of these n elements in O(n) time. Then to find pth smallest element it takes p(p-1)/2 comparisons i.e. constant time. So overall O(n).

Comments

So how is the answer O(n)? Please provide the answer,someone, anyone.

---

This answer is incorrect.

Even using min-heap or max-heap, the complexity should be $O(n + k \log n)$, and not $O(n)$.

Using QuickSelect, we can get it in $O(n)$ in average, but the worst case still remains the same of $O(n^2)$.

---

Yeah exactly @goxul. Can someone tell me how p(p-1)/2 comparisons for min heap?

Answer 2

answer should be log N bcoz it is given in question that array is sorted . so to find any element we can apply binary search.   will it works??

Answer 3

I Googled "linearly ordered" and it resulted in it meaning a TOSET. I don't know how a total order would be applicable here, tbh. If "linearly ordered" means "sorted" in an array here, then we can use random access and get the pth element in $O(1)$time. That isn't in the options.

Here's what I think is the answer.

Extracting the minimum element is what heap is for. So, build a min heap in $O(n)$ time.

After that extract the minimum element p times. Each such extraction would invoke heapify, and cost us $O(logn)$ time.

So, Time Complexity would be $O(n + plogn)$

In the worst case, p = n. So, $O(n + nlogn)$

=> $O(nlogn)$