|
Search: id:A159325
|
|
|
| A159325 |
|
Median number of comparisons used by insertion sort on n (distinct) elements |
|
+0
1
|
|
| 0, 1, 3, 5, 8, 11, 15, 19, 24, 30, 36, 42, 49, 56, 64, 73, 82, 91, 101, 111, 122, 134, 146, 158, 171, 185
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
The frequencies of the number of comparisons are given by sequence A129178, so if Sum_k=0..i-1 A129178(n,k) < n!/2 and Sum_k=0..i A129178(n,k) > n!/2, then the median is entry i, which corresponds to n(n-1)/2-i comparisons.
Close to average number of comparisons: A159324(n)/n!
|
|
EXAMPLE
|
For n=3, permutations 123,132,213,231,312,321 require 3,3,3,2,3,2 comparisons respectively, so the median is 3.
|
|
CROSSREFS
|
Cf. A129178, A159323, A159324
Sequence in context: A024169 A078126 A024206 this_sequence A049706 A080415 A014688
Adjacent sequences: A159322 A159323 A159324 this_sequence A159326 A159327 A159328
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Harmen Wassenaar (towr(AT)ai.rug.nl), Apr 10 2009
|
|
|
Search completed in 0.002 seconds
|
