|
| |
|
|
A067782
|
|
Minimal delay time for an n-element sorting network.
|
|
0
| |
|
|
0, 1, 3, 3, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| 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.
Sequence in context: A203998 A075260 A054847 * A035299 A021302 A004649
Adjacent sequences: A067779 A067780 A067781 * A067783 A067784 A067785
|
|
|
KEYWORD
| hard,nonn,nice
|
|
|
AUTHOR
| Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002
|
| |
|
|
