Re: Median: Oasis and Fast Sorting Algorithm

[Leonard Mada <discoleo gmx net>]

Uri David Akavia wrote:
> Admittedly, my complexity course is behind me, but there seem to be a
> few things wrong with your calculations of the efficiency.
> ...
> First, if you're using 2*n elements, shouldn't your results be nlog(n)
> instead of n/2*log(n)?

I used n elements for this calculation (such calculations are usually 
based on n; I used 2n only for the algorithm, to depict that n is even). 
So, considering that we start with n elemnts (NOT 2n):

n/2 * log(n) + log[(n/2 - 1)!] << n/2 * log(n) + log[(n/2)^(n/2)] = n * 
log(n) - n/2 (see also later, I believe I had a slight error in this 
formula, making it n * log(n), without -n/2)

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 
would fall inside the sorted array, so we can NOT drop them. So, T(n) < 
O(n log(n)), even IF I penalize for inserting one value into the sorted 
array as there would be maximum n/2 inserts and that should cancel out 
with (-n/2) [or add another n/2]. Also note, that as x[0] and x[last] 
are dropped, some of the new x[i] will be either < x[1], so replacing 
x[0] (NO or minimal cost) or > x[last -1], so replacing x[last], without 
cost. AND, most important, this sorted array shrinks with 1 element for 
every iteration, so at the end it consists of only 2 values (when we 
start with an even number of elements)!!!. Because the insert would mean 
moving a contiguous memory segment (NO need to create new array, because 
array is shrinking: insert 1, drop another 2 => array still shrink by 
one), this operation would be very fast.

These are of course approximations, and depend on the particular 
implementation.
> Third, you seem to have forgotten some actions when calculating - I
> realize that you're allowed to ignore some operations, but I'm not
> sure about these (again, please correct me if I'm wrong) - there are
> two comparisons for every item in the second half of the array,
> therefore you need to add 2*n actions.

NO, I added them up: (considering there are initially n elements)
- basic sort: (n/2 +1) log (n/2 + 1); assuming large n => n/2 + 1 ~ n/2
=> n/2 * log(n/2)
- second part: 2 comparisons for (n/2-1) elements: 2*(n/2-1) = n - 2
=> n/2 * log(n/2) + n -2 =~ n/2 log(2*n)  <----- It seems, I made here a 
mistake!!!!

Then the final calculation would yield O() < O(n * log(n)), that is, it 
is still smaller than n * log(n). (Hope, this is correct now.)

It must be faster, because the array is only half the initial length, 
and shrinks thereafter with one element per iteration, ending up with an 
array composed of only 2 values.

Please note, that, IF an accurate median is needed for an even number of 
elements (i.e. the average of the middle 2), this requires two calls to 
the routine, doubling the processing time, even for the Quick Search 
algorithm.

I would be interested, if anyone could check out, how fast this 
algorithm really is (i.e. real tests with a computer). I have no idea 
how this is done in practice.

Leonard