Maximum And Minimun

Question

There are n distinct numbers are given not in sorted order. How much time it will take to select a number say k which is neither k-th minimum nor k-th maximum.

A. O$(n)$

B. O$(1)$

C. O$(k)$

D. O$(k\log k)$.

Comments

can u plz explain k-th min and k-th max means. i'm nt getting.

---

take k = 3,

then the choosen element should not be 3rd min and max,

but it can be 1st/2nd min and max .

---

O(k) I think.

Answer 1

For this algorithm we have two cases$\Rightarrow$

case 1$\Rightarrow$when k$\geq$n

example$\Rightarrow ar\left [ 5 \right ]=\left \{ 5,4,3,2,1 \right \}$

Let $P\left ( x \right )=$Neither 5th Maximum nor 5th minimum .

$\Rightarrow$$\exists {\left ( P\left ( x \right )\right )}'$$\Rightarrow \Theta \left ( 1 \right )$

case 2:when k$< n$

step 1$\Rightarrow$Choose any subset of size $2k+1$

step 2$\Rightarrow$sort the Array $\Rightarrow \Theta \left ( k\log k \right )$

step 3$\Rightarrow$find the median ,it will be neither kth maximum nor kth minimum 

time complexity $T\left ( n \right )= k\log k$

example-:

https://gateoverflow.in/8113/gate2015-2_22 here k$< n$

so median can be found in $\Theta \left ( k \right )$

$T\left ( n \right )=\Theta \left ( k+k\log k \right )= \Theta \left ( k\log k \right )$

Comments

Can you please explain why the median of any subset of size $2k+1$ will neither be $k^{th}$ maximum nor $k^{th}$ minimum.

---

@prateekdewv because after sorting at left side of middle element exist kth minimum and right side exist kth maximum...it cant be at middle... best way to take any set try it...

---

@sourav anand ..In your first case find neither 3rd min nor max...??

---

yes in the first case check if k>n,then simply return.i.e no such element exists which is neither kth maximum nor kth minimum

---

@sourav anand

If you take any 2k + 1 elements and find its median, then itself it is neither the kth minimum nor maximum .

Finding median gives O(K) which is more optimal than sorting O(k lg k).

But, there are some drawbacks as it only good for 2k + 1 < N , what if 2k + 1 > N.

Then , finding median gives O(K) still, but actually it now covers the whole array , so it becomes O(N).

Hence, the question has 2 cases and some additional information must be given regarding this.

---

No, now you have the complete input N , and finding a median in this is O(N).