Made easy workbook

Question

Comments

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

Hi,

Initially, I also thought in the same lines but my query is, in this case, the worst case will now be when i=n/2, which means we have n/2 passes and thus overall T.C=O(n^2).

Also, if we keep considering i=n/2 as a constant and claim that to find n/2th min in an array we need worst T.C=O(n), then don't you think we are moving towards reducing the worst case time complexity of comparison based sorting of  a given array of number to O(n) [which we all know is O(nlogn) till date].

---

@Ayush

why do we need decending order sorting. Even in asceding order sorting it takes time O(n-1)=O(n)

---

Yes mamta your reasoning seems to be correct  and I made a mistake :(

Since it is given to assume n is larger than 50

if we have a very large array consisting of trillions of numbers and that too distinct then we can sort the array in best O(nlogn) time in the worst case and then directly provide the middle element.

---

@srestha-if you always wanted (n-1) smallest element, you could have given it in a faster way in either 2 passes of bubble sort which sorts number in ascending order or 2 passes of selection sort which sorts the number in descending order.

With each pass of bubble sort, the largest number goes towards the end and with each pass of selection sort , the smallest element comes forward.

---

@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