|
Search: id:A067782
|
|
|
| A067782 |
|
Minimal delay time for an n-element sorting network. |
|
+0
1
|
|
| 0, 1, 3, 3, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
Terms are exact for n<=9, otherwise best known (according to Knuth). Terms for n<=9 and n=11 are the delay-times for the sorting networks with the minimal number of comparisons (A003075).
|
|
REFERENCES
|
D. E. Knuth, Art of Computer Programming, Vol. 3, Sect. 5.3.4.
I. Parberry, "A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks", Mathematical Systems Theory, Vol. 24, pp. 101-116, 1991.
|
|
LINKS
|
Index entries for sequences related to sorting
|
|
CROSSREFS
|
Cf. A003075.
Adjacent sequences: A067779 A067780 A067781 this_sequence A067783 A067784 A067785
Sequence in context: A131507 A075260 A054847 this_sequence A035299 A021302 A004649
|
|
KEYWORD
|
hard,nonn,nice
|
|
AUTHOR
|
Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002
|
|
|
Search completed in 0.002 seconds
|
