Admittedly, my complexity course is behind me, but there seem to be a
few things wrong with your calculations of the efficiency. I'll try to
point out what I didn't like. If I'm wrong, please correct me.
On 2/10/07, Leonard Mada [EMAIL PROTECTED] wrote:
I have imagined a different algorithm,
Right, maybe my explanation was unclear. I'll try to repeat (and ask
other people to check my math).
On 2/10/07, Leonard Mada [EMAIL PROTECTED] wrote:
So, even in the worst scenario, this algorithm should work faster than
n* log(n). Also, (n/2 -1)! is worst case, when all residual elements
On Sat, 2007-10-02 at 02:41 +0200, Leonard Mada wrote:
John Machin wrote:
...
So who cares? The median value is 1. Is your alternative going to
return some value other than 1
Please define mathematically the middle value! It is NOT trivial as my
definitions showed. Anything else
Lets assume the following space A={1,2,3} [I do not know if it is called
space in English, probably NOT.]
Lets take the array 1,1,2,3,3,3
So the median is (2+3)/2 = 2.5 ? BUT the space A does NOT have the value
2.5. It is either 2 or 3. In this case, it is more appropriate to talk
about 2
On Sat, 2007-10-02 at 11:48 +0200, Uri David Akavia wrote:
While I'm not sure about revising the algorithm, you might be right
about the definition - define it as MEDIAN will return the value that
WOULD be in the middle IF sorted and then you won't force anyone to
sort. I still think most
Dear Uri,
you are very wrong.
I made some errors, too, so I repeat the calculations: (with n elements)
- initial sort: n/2 * log(n/2)
- 2 comparisons per remaining elements: 2*(n/2-1) = n - 2
- search position of new element: log[(n/2-1)!]log[(n/4)^(n/4)] =
n/4 * log(n/4)
- move array (with
Well, the OASIS formula has a big problem with situations like the
following:
data set is: 1,1,1. So the list contains 4 values of 1. So, the median
is the middle value, BUT there is really just one value repeated 3 times.
Or consider the following list: 1, 2, 2, 2, 3, 4. So the calculation of
On 10/02/2007 10:10 AM, Leonard Mada wrote:
Well, the OASIS formula has a big problem with situations like the
following:
data set is: 1,1,1. So the list contains 4 values of 1.
Looks like 3 to me, not 4. One of us has a big problem with the counting
algorithm :-)
So, the median
is the
The finding on the k-largest element in an unordered sequence of n elements is
a linear-time and (if memory serves) constant-space problem in terms of n.
See Knuth for details.
The trouble with the algorithm is that it is rather complicated. More
code means
more chances of bugs. Unless you are
