The Gateway to Computer Science Excellence
+2 votes
in Algorithms by (303 points) | 241 views
If the list has even or odd elements tat too does matter.

2 Answers

+1 vote
Best answer
it is B. O(n)....
by Active (3.8k points)
selected by
Please Explain...
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)...
But first U said its O(n).I m asking explanation for O(n)
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).
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.
0 votes
O (n)
by (11 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,385 answers
105,368 users