241 views
| 241 views
0
If the list has even or odd elements tat too does matter.

+1 vote
it is B. O(n)....
by Active (3.8k points)
selected by
0
+3
in order to find median, array should be sorted. so, in worst case firstly we have to sort the array which takes o(nlogn) then finding the median will take o(1).

hence total is o(nlogn) so (C)...
0
But first U said its O(n).I m asking explanation for O(n)
0
+2

it can be done without first sorting

0
In best case it is already sorted and using insertion sort it can be find out inin O(n) time . And further O(1) to find median.

So overall complexity for best case could be O(n).
0
Check out order statistics. There's $O(n)$ algorithm for finding rank of an element in $O(n)$ in worst case. Median of medians. Hence, the answer is B.
O (n)
by (11 points)

+1 vote