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

got confused with the term 'linearly ordered' which made me assume that the elements are already in an array, so was finding for O(1) in the options :)

Sir the question would be much more interesting if you could frame it as

" if n distinct elements need to be  added to a min heap , not necessarily one after the other to find the pth smallest element where ( 1≤ p ≤ n ) from these n elements when n > 50 . What is the worst case Time Complexity of the entire procedure."

---

what is linear order means?

---

@Bikram sir

What does "Linearly Ordered" means in this que??

Can I interprete Linearly ordered as a "set" which contains sorted distinct elements,then we have to make a build-heap which will take O(n) time then to find pth smallest element it takes p(p-1)/2 which is constant time. So overall time complexity is O(n).

Correct me sir if I m wrong

---

@shraddha How is p becoming a constant here?

---

@Arjun sir, In the question we are given 'p' and also that it lies between 1 to n, so it's a constant I think.

---

@Bikram sir, @Arjun sir

We have to find pth smallest element ( 1≤ p ≤ n ) from these n elements. So in worst case we have to find pth smallest element i.e. nth smallest element which is first maximum element. So in this scenario it will take n(n-1)/2 comparisons which is O(n²).

Plz correct me sir if I am wrong?

---

@shraddha no. Anything that is derived from input length - n - cannot be a constant. A constant is something which never changes whatever be the input.

---

@amit O(n^2) is obviously correct. But what happens when it becomes tight upper bound - theta? This is not so trivial and analogous to the complexity of build heap.

---

@Arjun sir

As it is given "n" number of linearly ordered distinct elements,so in worst case we have to find pth smallest element i.e. nth smallest element which will take O(n ) time, As it is the upper bound I think??

---

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)$