CODEWITHSUNDEEP
algorithmsortingmedian
evgniy tayarov
evgniy tayarov

Reputation: 77

Calculating median with a Black Box algorithm in O(n) time

the problem is this:

given an array A of size n and algorithm B and B(A,n)=b where b is an element of A such that |{1<=i<=n | a_i>b}|>=n/10
|{1<=i<=n | a_i>b}|<=n/10

The time complexity of B is O(n).

i need to find the median in O(n).

I tried solving this question by applying B and then finding the groups of elements that are smaller than b, lets name this group as C. and the elements bigger than b, lets name this group D. we can get groups C and D by traversing through array A in O(n). now i can apply algorithm B on the smaller group from the above because the median is not there and applying the same principle in the end i can get the median element. time complexity O(nlogn)

i can't seem to find a solution that works at O(n).

this is a homework question and i would appreciate any help or insight.

Upvotes: 1

Views: 362

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59368

You are supposed to use function B() to choose a pivot element for the Quickselect algorithm: https://en.wikipedia.org/wiki/Quickselect

It looks like you are already thinking of exactly this procedure, so you already have the algorithm, and you're just calculating the complexity incorrectly.

In each iteration, you run a linear time procedure on a list that is at most 9/10ths the size of the list in the previous iteration, so the worst case complexity is

O( n + n*0.9 + n*0.9^2 + n*0.9^3 ...)

Geometric progressions like this converge to a constant multiplier:

Let T = 1 + 0.9^1 + 0.9^2 + ...

It's easy to see that

T - T*0.9 = 1, so

T*(0.1) = 1, and T=10

So the total number of elements processed through all iterations is less than 10n, and your algorithm therefore takes O(n) time.

Upvotes: 3

Related Questions