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 _______________________________________________ gnumeric-list mailing list [email protected] http://mail.gnome.org/mailman/listinfo/gnumeric-list
