Propose an algorithm to find the median of an array A of siz

Propose an algorithm to find the median of an array A of size n in O(n) on the average case. You must show that your algorithm meets the O(n) complexity.

Solution

There is an algorithm called selection algorithm to find median in O(n).

It has 2 steps: first a pivot element is picked and elements are arranged such that the elements on left side of povot are lesser and on right are greater. Of course the pivot is in the apt position.

To find the median of our array, we must recursively call the partition function till the pivot reaches the middle position. Then we stop.

Hope this helps.