Finding Kth Smallest Element

Question

Which one  of the following is the recurrence equation for the worst case time complexity of finding Kth smallest element in an array of size ‘n’ using partition function? Assume ‘c’ is constant.

A. T(n) = 2T(n/2) + c . n

B. T(n) = 2T(n – 1) + c

C. (n) = T(n – 1) + c . n

D. T(n) = T(n/2) + c . n

Explanation Please and please tell me the different ways we can solve this problem

Comments

See

it is not given it is a sorted array. So, for unsorted array u need to verify every element . So, C) will be correct answer

If it is sorted array binary search can do the task

---

can you please explain or give a hint about how u will do it in case of unsorted array. Well i got for sorted array.

---

take array like 10,2,30,5,9

Now, need to find 3rd smallest element here.

So, u need to check every element in worst case

right?

---

Mam well i thought of one way, please tell weather its right.

We could use something like Quick sort strategy. i will choose a element. Apply the same Algorithm of quick sort only the difference that inside the for loop where we check that (A[j] <= Pivot)  then we will do count++ and suppose i picked up Kth smallest element then the if condition will execute K times(well we could modify the if condition accordingly i.e. >=  or  <= ) and if COUNT is exactly equal to K then we got that element else not.

in worst case K = N and the quick sort worst strategy we could assume.

Hence Time complexity ===>  T(n) = T(n-1) + C.n

Is it correct mam ?

---

why only quick sort, why not selection sort?

---

Oh yes well selection sort will be more easy then this. I got it thanku mam

---

Sort the array using merge sort and return the element present at $(k-1)^{th}$ index in the sorted array.
Recurrence equation will be -  $T(n) = 2T(\frac{n}{2}) + c . n$

---

Actually if u first sort then find the element then u have to time both work

U first done sorting

Now, u need to do search for Kth element

---

Yeah thats right mam but in question i suppose they're talking about finding Kth smallest by not using merge strategy but by partitioning them and checking every individual element i suppose.

In above solution of your's you are partitioning but for sorting.

---

@srestha But sorting then returning smallest element is more efficient. 

@Na462 Oh yeah. If this is the case then selection sort will work.
What is the source of the question? 

---

how will u do that?

again merging for finding kth smallest element?

---

@ Soumya it's a question from made easy :)

---

@srestha. why again merging?
I just used merge sort. Nothing else.

@Na462.. Ok.. :P

Answer 1

This question is for recurrence equation, so we have to apply divide and conquer approach. Finding Kth smallest element using divide and conquer algorithm is known as Selection procedure. Selection procedure is similar to quick sort partition algorithm. After every pass we will get one element at it's correct position. This position is nothing but smallest value at this position . Suppose after first pass we will get pivot element at 7th position so 7th smallest element is Pivot element.

Difference between quick sort and selection procedure is, in quick sort we will partitioning array in two parts but here we only partitioning array into one part. 

We will partitioning array into only one part because after every pass we exact know that either we will go at right partition or left partition.

Example :

15,25,10,85,75,95,87,5,6

Here we have 9 elements array and we want to find 3rd smallest number.

Now we apply partitioning algorithm and take pivot as first element

First pass output ---->6 10 5 [15] 75 95 87 23 85 ------>15 is at 4th position so 15 is 4th smallest but we want 3rd smallest so we will go to left partition and we have only three elements 6 10 5

Second pass output---->5 [6] 10 ----->6 is at 2nd position so 6 is 2nd smallest but we want 3rd smallest so we will go to right and we have only one element 10

So our 3rd smallest element is ----------->10

Now we all now that in worst case partition will be occur in (n-1) part so

T(n) = T(n – 1) + c . n

Comments

Can you please share the selection procedure? @Aditya Patel

 

Answer 2

option c is right.