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

@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