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

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