Arunachalam wrote:
> Search the groups, this problem is already solved in O(n) time in the
> groups.
>
> regards
> Arunachalam.
I solved it with n/2 case, I dont see how to do that with n/t, t
arbitrary.
Thanks
--~--~-~--~~~---~--~~
You received this message be
I think there should be an algorithm that uses the theta(n) finding
median subroutine. Somehow we divide and conquer, i.e. some
generalization of n/2 majority element case.
Thanks
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the G
Dear all,
I have worked out the following algorithm for finding the majority
element(the element occurs more than n/2 times) of an array of n
elements :
Suppose that I have a subroutine that could find the median of an array
in theta(n) time, then:
the algorithm will be:
1.find the median of th
Dear all,
I'm a bit stuck on my algorithm exercise, the problem asks us to
construct an algorithm that finds the median of an array in
theta(n^lg3) time. According the the Master Theorem
the recurrence relation of this algorithm should look like the
following:
T(n) = / theta(1) n =1
\ 3T(n/2) +