Algorithms

Question

Given n linearly ordered distinct elements. What is the worst case running time to find i^th  smallest element (1<=i<=n) from those n elements? 

a) O(log n)

b) O(n)

c) O(n log n)

d) O(n²)

Answer 1

Linearly ordered elements means that all elements are arranged or listed  have a particular relation. These elements can also be called as Partially ordered set(POSET). Ex:  $a\leq b\leq c$ or $a\geq b\geq c$.

i^th smallest element can be found by sorting. Best case here is if the elements are in a  relation $a\leq b\leq c$ i.e when all elements are sorted in asc order. Retrieving i^th smallest element would take constant time. But here we need worst case. Worst case scenario would be when elements have are in  $a\geq b\geq c$ i.e when elements are in desc order. So we need to sort the elements in asc order and then find  i^th element. Best sorting algorithms take O(n log n) time. 

So worst case time complexity for this problem would be, option C :  O(n log n)

Comments

Does nt it is the application of randomized quicksort in randomized quicksort when elements are in increasing order or decreasing order it is a worst case of randomized quicksort it should  be o(n^(2)) correct if I am wrong

Answer 2

O(n)

Comments

Can u explain how is it O(n).
Because below no one explain right thing .
If linearly order mean sorted doesn't matter asc or Dec Time complexity should be constant.
If not sorted than it goes to nlogn.
How is n possible ???

Answer 3

The worst case for this would be to traverse the array from i = 1 to n and stop when you've found the number equal to or greater than the number you're searching for.

Time Complexity: O(n)

Comments

But here it is given that array is linearly ordered. does it mean array is sorted ? 

---

I think O(n) but if it is already sorted time complexity is O(1)

---

how can u compare if we dont know the ith smallest element??say 3rd smallest number which we have 2 find not given by user.

---

we are searching for iTH small element which we dun know yet,so how can we search and stop at a particular point without knowing the number