[seqfan] Re: Computational Efficiency Sequences

[Heinz, Alois]

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