Made easy workbook

Question

Comments

O(nlogn)

---

Apply median of median algorithm..

 

U will get time complexity O(n) only

---

Suppose i=n then how much time will it take to find element in min heap tree

---

well than i will apply bubble sort...first pass..it will give n(th) minimum in O(n)..

---

for sorting,worst case time complexity take O(n²).

what is sorting?

finding 1^st minimum, 2^nd minimum,.... i^th minimum, .... (n-1)^th minimum, n^th minimum.

therefore i^th minimum takes O(n) only..

 

---

why you are ignoring the worst case time complexity(O(n^2)) for sorting.it is not given that number is in sorted.order???

---

@ BASANT KUMAR, i didn't ignore that the worst case time complexity(O(n²)) for sorting.

i gave the reason why it is O(n²).

 

i mean,due to find ith element in O(n), The worst case time complexity is O(n²)

---

Apply median of median algorithm...it will give time complexity O(n)

---

neerajyadav is right. There is an algorithm with O(n) running time in worst case to find the i^th smallest element in the input array of  size 'n' but it is difficult to explain here.

---

Can u provide link for that algorithm

---

i hope answer given in the manual is wrong.... it should be O( n log n )

https://gateoverflow.in/27194/tifr2014-b-9

---

@shaik brother How will it be O(n log n), I didn't get, please explain

---

As we need to go for tightest upper bound so nlogn  best possibility ....it can also be done in order of n

Answer 1

Here, worst case can occur if we want the $\frac{n}{2}^{th}$ smallest element and if you have a trillion of elements, you need to bother about your algorithm design.

 

So, one can think of like running $\frac{n}{2}$ passes of selection sort and giving answer as O(n), but it will be wrong because your $i$ can be anything ranging from 1 to n and if it is $\frac{n}{2}$ then, since each pass requires O(n), this will amount to total of

$\frac{n}{n}*n=O(n^2)$ considering n to be very large.

Now,I will look for the best algorithm that can sort my huge list of numbers and yes we have  O(nlogn) algorithms which can do that. So, once we have sorted our elements, we can return the $i^{th}$ smallest element in O(1) time amounting to a total runtime of O(nlogn)

Comments

@Ayush

u mean bubble and selection sort at same time??

---

each pass requires O(n)

u mean list is in descending order . Worst case means that. So, answer should be $O\left ( n^{2} \right )$ and not $O\left ( nlogn\right )$

right?

---

@srestha-No not at the same time. You could use any one of them if you always wanted $n-1^{th}$ smallest element every time in just O(2n) and that is O(n).

Answer 2

Array can be sorted in O(nlogn) & then i-th element can be found in O(1) using just index.

So, tightest bound of worst case ==> O(nlogn)

Comments

I also tried by same approach...but answer is given as O (n)

---

actually answer for abve qsn will be O(n) when you consider i as constant not function of n..than you will get b as answr by applying partition algo i times.i.e O(i*n)=O(n)....but in worst case i can also be equal to n...so than you can apply first pass of selection sort so that also gives O(n)..

so according to me answer would be O(n) only..please check.!

---

but,  O(nlogn) should be tighest bound of Worst case. (Use Merge sort!)

Answer 3

option : c is correct &  if in question mention that  (i<<n ) then option b is true