# Re: Median: Oasis and Fast Sorting Algorithm

*From*: Leonard Mada <discoleo gmx net>
*To*: gnumeric-list gnome org
*Subject*: Re: Median: Oasis and Fast Sorting Algorithm
*Date*: Sat, 10 Feb 2007 18:17:50 +0200

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

[

Date Prev][

Date Next] [

Thread Prev][

Thread Next]
[

Thread Index]
[

Date Index]
[

Author Index]