1,102 views

3 Answers

1 votes
1 votes

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

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

0 votes
0 votes
O(n)
0 votes
0 votes

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)

Related questions

0 votes
0 votes
1 answer
2
Overflow04 asked Oct 9, 2022
409 views
how O($n^{2}$) in the last.(in the given solution).
0 votes
0 votes
0 answers
3
Overflow04 asked Oct 9, 2022
277 views
Is it really coping operation will take O(n).Does copy is done character by character.means simple code like (in c++) for(int i=0;i<n;i++){s=s;}will take O($n^{2}$)