[seqfan] Re: Computational Efficiency Sequences

[Brad Klee]

Hi All,

Thanks for the responses.

With regard to the complexity functions, I simply mean to say that knowing
an algorithm is in O(n^3) doesn't give very much information regarding
related, exact sequences of "n".

Another list of sort sequences is found on the wiki (
http://oeis.org/wiki/Index_to_OEIS:_Section_So ).

I took a look at A001768, which counts comparisons in merge sort. After
doing some computations, I looked through the article and found out that
this sequence actually counts comparisons in Ford-Johnson sorting (
Allouche Shallit , Ex. 30 ).

If more keywords are ever added, maybe "comp" could describe sequences
related to computer science and / or algorithm complexity.

Reviewing my sequence from earlier, it seems possible to further reduce the
number of operations by skipping the first division at every iteration. It
is always the case that "a / a = 1".

Thanks,

Brad




On Sun, May 17, 2015 at 12:46 PM, Heinz, Alois <alois.heinz at hs-heilbronn.de>
wrote:

> Am 17.05.2015 um 00:37 schrieb Brad Klee:
> > Hi Seqfans,
> >
> > Just wondering if there are any sequences in the OEIS related to
> > computational efficiency? If so maybe there should be a list referencing
> > these series.
> >
> > I did a quick search, but found nothing....
>
> There are many.  Only a few examples:
>
> A001768 Sorting numbers: number of comparisons for merge sort of n elements
> A001855 Sorting numbers: maximal number of comparisons for sorting n
> elements by binary insertion
> A003071 Sorting numbers: maximal number of comparisons for sorting n
> elements by list merging
> A003075 Minimal number of comparisons needed for n-element sorting network
> A006282 Sorting numbers: number of comparisons in Batcher's parallel sort
> A036604 Sorting numbers: minimal number of comparisons needed to sort n
> elements
> A159324 n! times the average number of comparisons required by an
> insertion sort of n (distinct) elements.
> A212395 Number of move operations required to sort all permutations of
> [n] by insertion sort
> A014701 Number of multiplications to compute n-th power by the
> Chandah-sutra method
>
> Best regards, Alois
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>