0
votes
1answer
59 views

Give a randomized algorithm to find the median that has an expected number of comparisons = 2n + o(n)

Any help would be very much appreciated. I'm aware of 2 types of algorithms: "Median of the medians" and one using guards like here: http://www.cs.nthu.edu.tw/~wkhon/random12/lecture/lecture9.pdf ...
1
vote
1answer
563 views

Algorithm to separate an array of numbers into “low”, “medium” and “high” ranges

this is my first post on Math-Exchange. I'm a programmer, and I work with object-oriented algorithms, but when things gets too "algebraic" I get stuck. So I thought I'd ask over here. I need to ...
0
votes
1answer
562 views

Find median of 2 sorted arrays with different lengths

I'm trying to solve the below problem for my assignment but I have no clue how to find the time algorithm. If I have two arrays of same even length then I get, $T(n) = T(n/2) + \theta(n)$ but what ...
2
votes
1answer
1k views

Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm My ...
2
votes
2answers
54 views

Find factor of sample elements given the median

I have a sample $S(x)$ containing $n$ elements: $$S(x)=\{ s_1 x, s_2 x, \ldots, s_n x \},\qquad s_i \in \mathbb{R}, x\in \mathbb{R^{+}}$$ Every element in the sample is multiplied by $x$. Now ...