1657:
1768:
continuous or that are defined only over intervals of the real line; however, in this case, the points of discontinuity of the functions and the endpoints of the interval within which each function is defined add to the order of the sequence. For instance, a non-vertical line segment in the plane can
28:
of symbols in which the number of times any two symbols may appear in alternation is limited. The maximum possible length of a
Davenport–Schinzel sequence is bounded by the number of its distinct symbols multiplied by a small but nonconstant factor that depends on the number of alternations that are
145:
is a
Davenport–Schinzel sequence of order 3: it contains alternating subsequences of length four, such as ...1, ... 2, ... 1, ... 2, ... (which appears in four different ways as a subsequence of the whole sequence) but it does not contain any alternating subsequences of length five.
1543:
815:
1725:
within which one function has values smaller than all of the other functions. The sequence of these intervals, labeled by the minimizing function within each interval, forms a
Davenport–Schinzel sequence of order
679:
2371:
1781:
values, and the lower envelope of a collection of line segments forms a
Davenport–Schinzel sequence of order three because any two line segments can form an alternating subsequence with length at most four.
864:
595:
1296:
1138:
1061:
507:
1645:
1420:
1357:
1425:
987:
433:
937:
1212:
1584:
380:
336:
286:
is the
Ackermann function. Due to the very rapid growth of the Ackermann function, its inverse α grows very slowly, and is at most four for problems of any practical size.
1730:. Thus, any upper bound on the complexity of a Davenport–Schinzel sequence of this order also bounds the number of intervals in this representation of the lower envelope.
697:
1733:
In the original application of
Davenport and Schinzel, the functions under consideration were a set of different solutions to the same homogeneous
2272:
602:
2198:, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 49, American Mathematical Society, pp. 169–178
2381:
820:
2582:
530:
1217:
2577:
2271:
Nivasch, Gabriel (2009), "Improved bounds and new techniques for
Davenport–Schinzel sequences and their generalizations",
1067:
993:
2592:
1734:
38:
440:
2553:
1679:
1589:
2587:
1538:{\displaystyle \lambda _{s}(n)=\Omega \left(n\left({\frac {s}{2\log \log _{s}n}}\right)^{\log \log _{s}n}\right)}
1365:
1301:
509:. This complexity bound can be realized to within a factor of 2 by line segments: there exist arrangements of
943:
2156:
1722:
387:
50:
899:
1158:
105:
are two distinct values occurring in the sequence, then the sequence does not contain a subsequence ...
1551:
343:
299:
2522:
2291:
2315:
2147:(1986), "Nonlinearity of Davenport–Schinzel sequences and of generalized path compression schemes",
2161:
1770:
1714:
2204:
2512:
2495:
2477:
2307:
2281:
2182:
2123:
248:
2540:
2377:
2274:
Improved bounds and new techniques for
Davenport--Schinzel sequences and their generalizations
2237:
2036:(1989), "Sharp upper and lower bounds on the length of general Davenport–Schinzel sequences",
2025:
1656:
46:
2487:
2446:
2345:
2299:
2249:
2216:
2166:
2115:
2103:
2099:
2079:
2045:
810:{\displaystyle \lambda _{s}(n)=n\cdot 2^{{\frac {1}{t!}}\alpha (n)^{t}+O(\alpha (n)^{t-1})}}
34:
30:
2460:
2425:
2404:
2359:
2263:
2228:
2178:
2135:
2091:
2059:
2557:
2456:
2421:
2400:
2355:
2259:
2224:
2174:
2131:
2087:
2067:
2055:
1791:
2526:
2295:
1665:
1660:
A Davenport–Schinzel sequence of order 3 formed by the lower envelope of line segments.
514:
290:
2571:
2437:(1988), "Planar realizations of nonlinear Davenport–Schinzel sequences by segments",
2413:
2333:
2220:
2083:
2050:
17:
2468:
Pettie, Seth (2015), "Sharp bounds on
Davenport-Schinzel sequences of every order",
2186:
1764:
The same concept of a lower envelope can also be applied to functions that are only
1721:
values. With these assumptions, the real line can be partitioned into finitely many
2499:
2434:
2367:
2311:
2144:
2029:
2509:
Lower bounds on
Davenport-Schinzel sequences via rectangular Zarankiewicz matrices
2418:
Combinatorial theory and its applications, III (Proc. Colloq., Balatonfüred, 1969)
198:
2207:(1988), "A simplified construction of nonlinear Davenport–Schinzel sequences",
2033:
2194:
Klazar, M. (1999), "On the maximum lengths of Davenport–Schinzel sequences",
2544:
2350:
2336:; Stanton, R. G. (1971), "Some properties of Davenport-Schinzel sequences",
2303:
2254:
1765:
45:
these sequences and their length bounds have also become a standard tool in
2550:
1151:
the upper and lower bounds on Davenport-Schinzel sequences are not tight.
2106:(1965), "A combinatorial problem connected with differential equations",
1713:
Suppose that these functions are particularly well behaved: they are all
25:
2391:
Stanton, R. G.; Dirksen, P. H. (1976), "Davenport-Schinzel sequences.",
2451:
2170:
2127:
2491:
2119:
29:
allowed. Davenport–Schinzel sequences were first defined in 1965 by
2517:
2482:
2286:
674:{\displaystyle \lambda _{5}(n)=\Theta (n\alpha (n)2^{\alpha (n)})}
94:
No two consecutive values in the sequence are equal to each other.
209:
is a fixed constant, and nearly tight bounds are known for all
2373:
Davenport–Schinzel Sequences and Their Geometric Applications
1115:
1041:
859:{\displaystyle t=\left\lfloor {\frac {s-2}{2}}\right\rfloor }
2238:"A map-theoretic approach to Davenport-Schinzel sequences."
2070:(1985), "Some dynamic computational geometry problems",
590:{\displaystyle \lambda _{4}(n)=\Theta (n2^{\alpha (n)})}
86:, is said to be a Davenport–Schinzel sequence of order
1291:{\displaystyle \lambda _{s}(n)=\Omega (n^{2}s/(t-1)!)}
1592:
1554:
1428:
1368:
1304:
1220:
1161:
1070:
996:
946:
902:
823:
700:
605:
533:
443:
390:
346:
302:
2416:(1970), "A result on Davenport-Schinzel sequences",
1745:
values in common, so the lower envelope of a set of
1133:{\displaystyle \lambda _{s}(4)=6s-2+(s{\bmod {2}}).}
1056:{\displaystyle \lambda _{s}(3)=3s-2+(s{\bmod {2}})}
2114:(3), The Johns Hopkins University Press: 684–694,
1685:is the function given by their pointwise minimum:
1639:
1578:
1537:
1414:
1351:
1290:
1206:
1132:
1055:
981:
931:
858:
809:
673:
589:
501:
427:
374:
330:
1949:
1913:
502:{\displaystyle \lambda _{3}(n)=2n\alpha (n)+O(n)}
2420:, Amsterdam: North-Holland, pp. 1023–1027,
1640:{\displaystyle \lambda _{s}(n)=\Omega (n2^{s})}
1981:
1969:
1741:. Any two distinct solutions can have at most
90:if it satisfies the following two properties:
2009:
1997:
1985:
1945:
1909:
1897:
1893:
1861:
1849:
1834:
1822:
1809:
8:
2196:Contemporary Trends in Discrete Mathematics
2072:Computers and Mathematics with Applications
1717:, and any two of them are equal on at most
205:goes to infinity, with the assumption that
1865:
149:If a Davenport–Schinzel sequence of order
125: + 2 values alternating between
2516:
2481:
2450:
2349:
2285:
2253:
2209:Journal of Combinatorial Theory, Series A
2160:
2049:
2038:Journal of Combinatorial Theory, Series A
1628:
1597:
1591:
1553:
1516:
1505:
1486:
1467:
1433:
1427:
1415:{\displaystyle \log \log n<s=n^{o(1)}}
1397:
1367:
1352:{\displaystyle \lambda _{s}(n)=O(n^{2}s)}
1337:
1309:
1303:
1262:
1253:
1225:
1219:
1176:
1172:
1160:
1118:
1114:
1075:
1069:
1044:
1040:
1001:
995:
978:
951:
945:
928:
907:
901:
834:
822:
790:
762:
734:
733:
705:
699:
653:
610:
604:
569:
538:
532:
448:
442:
395:
389:
351:
345:
307:
301:
1655:
1953:
1917:
1877:
1869:
1802:
42:
2507:Wellman, Julian; Pettie, Seth (2016),
2236:Mullin, R. C.; Stanton, R. G. (1972),
1957:
1933:
1921:
1881:
1873:
1845:
1843:
2439:Discrete & Computational Geometry
982:{\displaystyle \lambda _{s}(2)=s+1\,}
238:)-sequence. The best bounds known on
141:1, 2, 1, 3, 1, 3, 2, 4, 5, 4, 5, 2, 3
7:
428:{\displaystyle \lambda _{2}(n)=2n-1}
165:) Davenport–Schinzel sequence, or a
932:{\displaystyle \lambda _{s}(1)=1\,}
226:) denote the length of the longest
1615:
1451:
1243:
1207:{\displaystyle s>n^{1/t}(t-1)!}
628:
556:
293:, the following bounds are known:
157:distinct values, it is called an (
14:
1950:Agarwal, Sharir & Shor (1989)
1914:Agarwal, Sharir & Shor (1989)
1579:{\displaystyle s\leq \log \log n}
513:line segments in the plane whose
375:{\displaystyle \lambda _{1}(n)=n}
331:{\displaystyle \lambda _{0}(n)=1}
684:For both even and odd values of
2280:, vol. 57, pp. 1–10,
2108:American Journal of Mathematics
2376:, Cambridge University Press,
2242:Pacific Journal of Mathematics
1777:values to their corresponding
1652:Application to lower envelopes
1634:
1618:
1609:
1603:
1445:
1439:
1407:
1401:
1346:
1330:
1321:
1315:
1285:
1279:
1267:
1246:
1237:
1231:
1198:
1186:
1124:
1108:
1087:
1081:
1050:
1034:
1013:
1007:
963:
957:
919:
913:
802:
787:
780:
774:
759:
752:
717:
711:
668:
663:
657:
646:
640:
631:
622:
616:
584:
579:
573:
559:
550:
544:
496:
490:
481:
475:
460:
454:
407:
401:
363:
357:
319:
313:
1:
2370:; Agarwal, Pankaj K. (1995),
197:)-sequence has been analyzed
39:linear differential equations
2551:Davenport-Schinzel Sequences
2221:10.1016/0097-3165(88)90055-6
2084:10.1016/0898-1221(85)90105-1
2051:10.1016/0097-3165(89)90032-0
1982:Roselle & Stanton (1971)
1970:Roselle & Stanton (1971)
1735:linear differential equation
2541:Davenport-Schinzel Sequence
2010:Wellman & Pettie (2016)
1998:Wellman & Pettie (2016)
1986:Wellman & Pettie (2016)
1946:Sharir & Agarwal (1995)
1910:Sharir & Agarwal (1995)
1898:Wiernik & Sharir (1988)
1894:Sharir & Agarwal (1995)
1862:Sharir & Agarwal (1995)
1850:Sharir & Agarwal (1995)
1835:Sharir & Agarwal (1995)
1823:Sharir & Agarwal (1995)
1810:Sharir & Agarwal (1995)
1749:distinct solutions forms a
137:For instance, the sequence
22:Davenport–Schinzel sequence
2609:
1825:, p. 1, for this notation.
249:inverse Ackermann function
1896:, Chapter 4, pp. 86–114;
2560:, a section in the book
1948:, Chapter 3, pp. 43–85;
1912:, Chapter 3, pp. 43–85;
1866:Hart & Sharir (1986)
1864:, Chapter 2, pp. 12–42;
291:big O and big Θ notation
2564:, by Steven M. LaValle.
2351:10.4064/aa-17-4-355-362
2304:10.1145/1706591.1706597
2255:10.2140/pjm.1972.40.167
1773:mapping an interval of
1668:of a set of functions ƒ
49:and in the analysis of
2583:Combinatorics on words
1769:be interpreted as the
1661:
1641:
1580:
1539:
1416:
1353:
1292:
1208:
1134:
1057:
983:
933:
860:
811:
675:
591:
503:
429:
376:
332:
1659:
1642:
1581:
1540:
1417:
1354:
1293:
1209:
1135:
1058:
984:
934:
893:is a small constant:
885:) is also known when
861:
812:
676:
592:
504:
430:
377:
333:
2578:Sequences and series
1590:
1552:
1426:
1366:
1302:
1218:
1159:
1068:
994:
944:
900:
821:
698:
603:
531:
441:
388:
344:
300:
121:, ... consisting of
51:geometric algorithms
2593:Eponyms in geometry
2527:2016arXiv161009774W
2296:2008arXiv0807.0484N
2068:Atallah, Mikhail J.
1771:graph of a function
2556:2020-01-13 at the
2452:10.1007/BF02187894
2171:10.1007/BF02579170
1662:
1637:
1576:
1535:
1412:
1349:
1288:
1204:
1130:
1053:
979:
929:
856:
807:
671:
587:
517:have complexity Ω(
499:
425:
372:
328:
185:The complexity of
61:A finite sequence
2588:Discrete geometry
2104:Schinzel, Andrzej
2078:(12): 1171–1181,
1693:) = min
1499:
1147:is a function of
850:
747:
47:discrete geometry
2600:
2529:
2520:
2502:
2485:
2463:
2454:
2428:
2412:Stanton, R. G.;
2407:
2393:Ars Combinatoria
2386:
2362:
2353:
2338:Acta Arithmetica
2328:
2327:
2326:
2320:
2314:, archived from
2289:
2279:
2266:
2257:
2231:
2199:
2189:
2164:
2138:
2094:
2062:
2053:
2013:
2007:
2001:
1995:
1989:
1979:
1973:
1967:
1961:
1943:
1937:
1931:
1925:
1907:
1901:
1891:
1885:
1859:
1853:
1847:
1838:
1832:
1826:
1819:
1813:
1807:
1646:
1644:
1643:
1638:
1633:
1632:
1602:
1601:
1585:
1583:
1582:
1577:
1544:
1542:
1541:
1536:
1534:
1530:
1529:
1528:
1521:
1520:
1504:
1500:
1498:
1491:
1490:
1468:
1438:
1437:
1421:
1419:
1418:
1413:
1411:
1410:
1358:
1356:
1355:
1350:
1342:
1341:
1314:
1313:
1297:
1295:
1294:
1289:
1266:
1258:
1257:
1230:
1229:
1213:
1211:
1210:
1205:
1185:
1184:
1180:
1139:
1137:
1136:
1131:
1123:
1122:
1080:
1079:
1062:
1060:
1059:
1054:
1049:
1048:
1006:
1005:
988:
986:
985:
980:
956:
955:
938:
936:
935:
930:
912:
911:
889:is variable but
865:
863:
862:
857:
855:
851:
846:
835:
816:
814:
813:
808:
806:
805:
801:
800:
767:
766:
748:
746:
735:
710:
709:
680:
678:
677:
672:
667:
666:
615:
614:
596:
594:
593:
588:
583:
582:
543:
542:
508:
506:
505:
500:
453:
452:
434:
432:
431:
426:
400:
399:
381:
379:
378:
373:
356:
355:
337:
335:
334:
329:
312:
311:
201:in the limit as
35:Andrzej Schinzel
31:Harold Davenport
2608:
2607:
2603:
2602:
2601:
2599:
2598:
2597:
2568:
2567:
2562:Motion Planning
2558:Wayback Machine
2537:
2506:
2492:10.1145/2794075
2467:
2432:
2411:
2390:
2384:
2366:
2332:
2324:
2322:
2318:
2277:
2270:
2235:
2203:
2193:
2142:
2120:10.2307/2373068
2098:
2066:
2024:
2021:
2016:
2008:
2004:
1996:
1992:
1980:
1976:
1968:
1964:
1944:
1940:
1932:
1928:
1908:
1904:
1892:
1888:
1860:
1856:
1848:
1841:
1833:
1829:
1820:
1816:
1808:
1804:
1800:
1792:Squarefree word
1788:
1704:
1698:
1673:
1654:
1624:
1593:
1588:
1587:
1550:
1549:
1512:
1482:
1472:
1463:
1462:
1458:
1454:
1429:
1424:
1423:
1393:
1364:
1363:
1333:
1305:
1300:
1299:
1249:
1221:
1216:
1215:
1168:
1157:
1156:
1071:
1066:
1065:
997:
992:
991:
947:
942:
941:
903:
898:
897:
880:
836:
830:
819:
818:
786:
758:
739:
729:
701:
696:
695:
649:
606:
601:
600:
565:
534:
529:
528:
515:lower envelopes
444:
439:
438:
391:
386:
385:
347:
342:
341:
303:
298:
297:
246:
221:
183:
85:
78:
71:
59:
12:
11:
5:
2606:
2604:
2596:
2595:
2590:
2585:
2580:
2570:
2569:
2566:
2565:
2548:
2536:
2535:External links
2533:
2532:
2531:
2504:
2465:
2433:Wiernik, Ady;
2430:
2414:Roselle, D. P.
2409:
2388:
2382:
2364:
2344:(4): 355–362,
2334:Roselle, D. P.
2330:
2268:
2233:
2215:(2): 262–267,
2205:Komjáth, Péter
2201:
2191:
2162:10.1.1.295.885
2155:(2): 151–177,
2140:
2096:
2064:
2044:(2): 228–274,
2026:Agarwal, P. K.
2020:
2017:
2015:
2014:
2002:
1990:
1974:
1962:
1954:Nivasch (2009)
1938:
1926:
1918:Nivasch (2009)
1902:
1886:
1878:Nivasch (2009)
1870:Komjáth (1988)
1854:
1839:
1827:
1814:
1812:, pp. x and 2.
1801:
1799:
1796:
1795:
1794:
1787:
1784:
1711:
1710:
1700:
1694:
1669:
1666:lower envelope
1653:
1650:
1649:
1648:
1636:
1631:
1627:
1623:
1620:
1617:
1614:
1611:
1608:
1605:
1600:
1596:
1575:
1572:
1569:
1566:
1563:
1560:
1557:
1546:
1533:
1527:
1524:
1519:
1515:
1511:
1508:
1503:
1497:
1494:
1489:
1485:
1481:
1478:
1475:
1471:
1466:
1461:
1457:
1453:
1450:
1447:
1444:
1441:
1436:
1432:
1409:
1406:
1403:
1400:
1396:
1392:
1389:
1386:
1383:
1380:
1377:
1374:
1371:
1360:
1348:
1345:
1340:
1336:
1332:
1329:
1326:
1323:
1320:
1317:
1312:
1308:
1287:
1284:
1281:
1278:
1275:
1272:
1269:
1265:
1261:
1256:
1252:
1248:
1245:
1242:
1239:
1236:
1233:
1228:
1224:
1203:
1200:
1197:
1194:
1191:
1188:
1183:
1179:
1175:
1171:
1167:
1164:
1141:
1140:
1129:
1126:
1121:
1117:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1086:
1083:
1078:
1074:
1063:
1052:
1047:
1043:
1039:
1036:
1033:
1030:
1027:
1024:
1021:
1018:
1015:
1012:
1009:
1004:
1000:
989:
977:
974:
971:
968:
965:
962:
959:
954:
950:
939:
927:
924:
921:
918:
915:
910:
906:
876:
870:
869:
868:
867:
854:
849:
845:
842:
839:
833:
829:
826:
804:
799:
796:
793:
789:
785:
782:
779:
776:
773:
770:
765:
761:
757:
754:
751:
745:
742:
738:
732:
728:
725:
722:
719:
716:
713:
708:
704:
690:
689:
682:
670:
665:
662:
659:
656:
652:
648:
645:
642:
639:
636:
633:
630:
627:
624:
621:
618:
613:
609:
598:
586:
581:
578:
575:
572:
568:
564:
561:
558:
555:
552:
549:
546:
541:
537:
526:
498:
495:
492:
489:
486:
483:
480:
477:
474:
471:
468:
465:
462:
459:
456:
451:
447:
436:
424:
421:
418:
415:
412:
409:
406:
403:
398:
394:
383:
371:
368:
365:
362:
359:
354:
350:
339:
327:
324:
321:
318:
315:
310:
306:
280:
279:
242:
217:
199:asymptotically
182:
179:
143:
142:
135:
134:
95:
83:
76:
69:
58:
55:
43:Atallah (1985)
13:
10:
9:
6:
4:
3:
2:
2605:
2594:
2591:
2589:
2586:
2584:
2581:
2579:
2576:
2575:
2573:
2563:
2559:
2555:
2552:
2549:
2546:
2542:
2539:
2538:
2534:
2528:
2524:
2519:
2514:
2510:
2505:
2501:
2497:
2493:
2489:
2484:
2479:
2475:
2471:
2466:
2462:
2458:
2453:
2448:
2444:
2440:
2436:
2435:Sharir, Micha
2431:
2427:
2423:
2419:
2415:
2410:
2406:
2402:
2398:
2394:
2389:
2385:
2383:0-521-47025-0
2379:
2375:
2374:
2369:
2368:Sharir, Micha
2365:
2361:
2357:
2352:
2347:
2343:
2339:
2335:
2331:
2321:on 2012-10-18
2317:
2313:
2309:
2305:
2301:
2297:
2293:
2288:
2283:
2276:
2275:
2269:
2265:
2261:
2256:
2251:
2247:
2243:
2239:
2234:
2230:
2226:
2222:
2218:
2214:
2210:
2206:
2202:
2197:
2192:
2188:
2184:
2180:
2176:
2172:
2168:
2163:
2158:
2154:
2150:
2149:Combinatorica
2146:
2145:Sharir, Micha
2141:
2137:
2133:
2129:
2125:
2121:
2117:
2113:
2109:
2105:
2101:
2100:Davenport, H.
2097:
2093:
2089:
2085:
2081:
2077:
2073:
2069:
2065:
2061:
2057:
2052:
2047:
2043:
2039:
2035:
2031:
2030:Sharir, Micha
2027:
2023:
2022:
2018:
2011:
2006:
2003:
1999:
1994:
1991:
1987:
1983:
1978:
1975:
1971:
1966:
1963:
1959:
1958:Pettie (2015)
1955:
1951:
1947:
1942:
1939:
1935:
1934:Pettie (2015)
1930:
1927:
1923:
1922:Pettie (2015)
1919:
1915:
1911:
1906:
1903:
1899:
1895:
1890:
1887:
1883:
1882:Pettie (2015)
1879:
1875:
1874:Klazar (1999)
1871:
1867:
1863:
1858:
1855:
1851:
1846:
1844:
1840:
1836:
1831:
1828:
1824:
1818:
1815:
1811:
1806:
1803:
1797:
1793:
1790:
1789:
1785:
1783:
1780:
1776:
1772:
1767:
1762:
1760:
1756:
1752:
1748:
1744:
1740:
1736:
1731:
1729:
1724:
1720:
1716:
1708:
1703:
1697:
1692:
1688:
1687:
1686:
1684:
1681:
1680:real variable
1677:
1672:
1667:
1658:
1651:
1629:
1625:
1621:
1612:
1606:
1598:
1594:
1573:
1570:
1567:
1564:
1561:
1558:
1555:
1547:
1531:
1525:
1522:
1517:
1513:
1509:
1506:
1501:
1495:
1492:
1487:
1483:
1479:
1476:
1473:
1469:
1464:
1459:
1455:
1448:
1442:
1434:
1430:
1404:
1398:
1394:
1390:
1387:
1384:
1381:
1378:
1375:
1372:
1369:
1361:
1343:
1338:
1334:
1327:
1324:
1318:
1310:
1306:
1282:
1276:
1273:
1270:
1263:
1259:
1254:
1250:
1240:
1234:
1226:
1222:
1201:
1195:
1192:
1189:
1181:
1177:
1173:
1169:
1165:
1162:
1154:
1153:
1152:
1150:
1146:
1127:
1119:
1111:
1105:
1102:
1099:
1096:
1093:
1090:
1084:
1076:
1072:
1064:
1045:
1037:
1031:
1028:
1025:
1022:
1019:
1016:
1010:
1002:
998:
990:
975:
972:
969:
966:
960:
952:
948:
940:
925:
922:
916:
908:
904:
896:
895:
894:
892:
888:
884:
879:
875:
872:The value of
852:
847:
843:
840:
837:
831:
827:
824:
797:
794:
791:
783:
777:
771:
768:
763:
755:
749:
743:
740:
736:
730:
726:
723:
720:
714:
706:
702:
694:
693:
692:
691:
687:
683:
660:
654:
650:
643:
637:
634:
625:
619:
611:
607:
599:
576:
570:
566:
562:
553:
547:
539:
535:
527:
524:
520:
516:
512:
493:
487:
484:
478:
472:
469:
466:
463:
457:
449:
445:
437:
422:
419:
416:
413:
410:
404:
396:
392:
384:
369:
366:
360:
352:
348:
340:
325:
322:
316:
308:
304:
296:
295:
294:
292:
287:
285:
277:
273:
269:
265:
261:
257:
253:
252:
251:
250:
245:
241:
237:
233:
229:
225:
220:
216:
212:
208:
204:
200:
196:
192:
188:
181:Length bounds
180:
178:
176:
172:
168:
164:
160:
156:
152:
147:
140:
139:
138:
132:
128:
124:
120:
116:
112:
108:
104:
100:
96:
93:
92:
91:
89:
82:
75:
68:
64:
56:
54:
52:
48:
44:
40:
36:
32:
27:
23:
19:
18:combinatorics
2561:
2508:
2473:
2469:
2445:(1): 15–47,
2442:
2438:
2417:
2399:(1): 43–51,
2396:
2392:
2372:
2341:
2337:
2323:, retrieved
2316:the original
2273:
2245:
2241:
2212:
2208:
2195:
2152:
2148:
2111:
2107:
2075:
2071:
2041:
2037:
2005:
1993:
1977:
1965:
1941:
1929:
1905:
1889:
1857:
1830:
1817:
1805:
1778:
1774:
1763:
1761:)-sequence.
1758:
1754:
1750:
1746:
1742:
1738:
1732:
1727:
1718:
1712:
1706:
1701:
1695:
1690:
1682:
1675:
1670:
1663:
1148:
1144:
1142:
890:
886:
882:
877:
873:
871:
685:
522:
518:
510:
288:
283:
281:
275:
271:
267:
263:
259:
255:
247:involve the
243:
239:
235:
231:
227:
223:
218:
214:
210:
206:
202:
194:
190:
186:
184:
177:)-sequence.
174:
170:
166:
162:
158:
154:
150:
148:
144:
136:
130:
126:
122:
118:
114:
110:
106:
102:
98:
87:
80:
73:
66:
62:
60:
41:. Following
21:
15:
2476:(5): 1–40,
2248:: 167–172,
37:to analyze
2572:Categories
2518:1610.09774
2325:2009-01-08
2143:Hart, S.;
2019:References
1715:continuous
258:) = min {
57:Definition
2545:MathWorld
2483:1204.1086
2287:0807.0484
2157:CiteSeerX
1766:piecewise
1737:of order
1723:intervals
1616:Ω
1595:λ
1571:
1565:
1559:≤
1523:
1510:
1493:
1480:
1452:Ω
1431:λ
1379:
1373:
1307:λ
1274:−
1244:Ω
1223:λ
1193:−
1100:−
1073:λ
1026:−
999:λ
949:λ
905:λ
841:−
795:−
778:α
750:α
727:⋅
703:λ
655:α
638:α
629:Θ
608:λ
571:α
557:Θ
536:λ
473:α
446:λ
420:−
393:λ
349:λ
305:λ
153:includes
2554:Archived
2187:18864716
2034:Shor, P.
1837:, p. 14.
1786:See also
853:⌋
832:⌊
817:, where
521: α(
26:sequence
2543:, from
2523:Bibcode
2500:6880266
2461:0918177
2426:0304189
2405:0409347
2360:0284414
2312:3175575
2292:Bibcode
2264:0302601
2229:0964387
2179:0875839
2136:0190010
2128:2373068
2092:0822083
2060:1022320
1852:, p. 6.
1678:) of a
117:, ...,
113:, ...,
2498:
2470:J. ACM
2459:
2424:
2403:
2380:
2358:
2310:
2262:
2227:
2185:
2177:
2159:
2134:
2126:
2090:
2058:
289:Using
282:where
213:. Let
109:, ...
2513:arXiv
2496:S2CID
2478:arXiv
2319:(PDF)
2308:S2CID
2282:arXiv
2278:(PDF)
2183:S2CID
2124:JSTOR
1798:Notes
1548:When
1362:When
1155:When
1143:When
24:is a
2378:ISBN
1821:See
1664:The
1385:<
1298:and
1166:>
688:≥ 6,
274:) ≥
129:and
101:and
33:and
20:, a
2488:doi
2447:doi
2346:doi
2300:doi
2250:doi
2217:doi
2167:doi
2116:doi
2080:doi
2046:doi
1568:log
1562:log
1514:log
1507:log
1484:log
1477:log
1422:,
1376:log
1370:log
1116:mod
1042:mod
525:)).
97:If
16:In
2574::
2521:,
2511:,
2494:,
2486:,
2474:62
2472:,
2457:MR
2455:,
2441:,
2422:MR
2401:MR
2395:,
2356:MR
2354:,
2342:17
2340:,
2306:,
2298:,
2290:,
2260:MR
2258:,
2246:40
2244:,
2240:,
2225:MR
2223:,
2213:49
2211:,
2181:,
2175:MR
2173:,
2165:,
2151:,
2132:MR
2130:,
2122:,
2112:87
2110:,
2102:;
2088:MR
2086:,
2076:11
2074:,
2056:MR
2054:,
2042:52
2040:,
2032:;
2028:;
1984:;
1956:;
1952:;
1920:;
1916:;
1880:;
1876:;
1872:;
1868:;
1842:^
1751:DS
1709:).
1689:ƒ(
1586:,
1214:,
278:},
262:|
254:α(
228:DS
187:DS
167:DS
79:,
72:,
65:=
53:.
2547:.
2530:.
2525::
2515::
2503:.
2490::
2480::
2464:.
2449::
2443:3
2429:.
2408:.
2397:1
2387:.
2363:.
2348::
2329:.
2302::
2294::
2284::
2267:.
2252::
2232:.
2219::
2200:.
2190:.
2169::
2153:6
2139:.
2118::
2095:.
2082::
2063:.
2048::
2012:.
2000:.
1988:.
1972:.
1960:.
1936:.
1924:.
1900:.
1884:.
1779:y
1775:x
1759:s
1757:,
1755:n
1753:(
1747:n
1743:s
1739:s
1728:s
1719:s
1707:x
1705:(
1702:i
1699:ƒ
1696:i
1691:x
1683:x
1676:x
1674:(
1671:i
1647:.
1635:)
1630:s
1626:2
1622:n
1619:(
1613:=
1610:)
1607:n
1604:(
1599:s
1574:n
1556:s
1545:.
1532:)
1526:n
1518:s
1502:)
1496:n
1488:s
1474:2
1470:s
1465:(
1460:n
1456:(
1449:=
1446:)
1443:n
1440:(
1435:s
1408:)
1405:1
1402:(
1399:o
1395:n
1391:=
1388:s
1382:n
1359:.
1347:)
1344:s
1339:2
1335:n
1331:(
1328:O
1325:=
1322:)
1319:n
1316:(
1311:s
1286:)
1283:!
1280:)
1277:1
1271:t
1268:(
1264:/
1260:s
1255:2
1251:n
1247:(
1241:=
1238:)
1235:n
1232:(
1227:s
1202:!
1199:)
1196:1
1190:t
1187:(
1182:t
1178:/
1174:1
1170:n
1163:s
1149:n
1145:s
1128:.
1125:)
1120:2
1112:s
1109:(
1106:+
1103:2
1097:s
1094:6
1091:=
1088:)
1085:4
1082:(
1077:s
1051:)
1046:2
1038:s
1035:(
1032:+
1029:2
1023:s
1020:3
1017:=
1014:)
1011:3
1008:(
1003:s
976:1
973:+
970:s
967:=
964:)
961:2
958:(
953:s
926:1
923:=
920:)
917:1
914:(
909:s
891:n
887:s
883:n
881:(
878:s
874:λ
866:.
848:2
844:2
838:s
828:=
825:t
803:)
798:1
792:t
788:)
784:n
781:(
775:(
772:O
769:+
764:t
760:)
756:n
753:(
744:!
741:t
737:1
731:2
724:n
721:=
718:)
715:n
712:(
707:s
686:s
681:.
669:)
664:)
661:n
658:(
651:2
647:)
644:n
641:(
635:n
632:(
626:=
623:)
620:n
617:(
612:5
597:.
585:)
580:)
577:n
574:(
567:2
563:n
560:(
554:=
551:)
548:n
545:(
540:4
523:n
519:n
511:n
497:)
494:n
491:(
488:O
485:+
482:)
479:n
476:(
470:n
467:2
464:=
461:)
458:n
455:(
450:3
435:.
423:1
417:n
414:2
411:=
408:)
405:n
402:(
397:2
382:.
370:n
367:=
364:)
361:n
358:(
353:1
338:.
326:1
323:=
320:)
317:n
314:(
309:0
284:A
276:n
272:m
270:,
268:m
266:(
264:A
260:m
256:n
244:s
240:λ
236:s
234:,
232:n
230:(
224:n
222:(
219:s
215:λ
211:s
207:s
203:n
195:s
193:,
191:n
189:(
175:s
173:,
171:n
169:(
163:s
161:,
159:n
155:n
151:s
133:.
131:y
127:x
123:s
119:y
115:x
111:y
107:x
103:y
99:x
88:s
84:3
81:u
77:2
74:u
70:1
67:u
63:U
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
