[seqfan] Re: Computational Efficiency Sequences
Heinz, Alois
alois.heinz at hs-heilbronn.de
Sun May 17 19:46:15 CEST 2015
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
More information about the SeqFan
mailing list