2778:
341:
31:
3355:
3084:
6350:) that will express how long the algorithm will take to run (in some arbitrary measurement of time) in terms of the number of elements in the input set. The algorithm works by first calling a subroutine to sort the elements in the set and then perform its own operations. The sort has a known time complexity of
17634:) in Waring's problem" (Russian). Doklady Akademii Nauk SSSR 5, No 5-6 (1934), 249–253. Translated in English in: Selected works / Ivan Matveevič Vinogradov; prepared by the Steklov Mathematical Institute of the Academy of Sciences of the USSR on the occasion of his 90th birthday. Springer-Verlag, 1985.
6712:
14222:
14577:
effects of some other super-logarithmic function indicate a growth-rate explosion for large-sized input parameters that is more important to predicting bad run-time performance than the finer-point effects contributed by the logarithmic-growth factor(s). This notation is often used to obviate the
2924:. Additionally, the number of steps depends on the details of the machine model on which the algorithm runs, but different types of machines typically vary by only a constant factor in the number of steps needed to execute an algorithm. So the big O notation captures what remains: we write either
17337:
When the asymptotic notation stands alone (that is, not within a larger formula) on the right-hand side of an equation (or inequality), as in n = O(n), we have already defined the equal sign to mean set membership: n ∈ O(n). In general, however, when asymptotic notation appears in a formula, we
14226:
The authors state that the use of equality operator (=) to denote set membership rather than the set membership operator (∈) is an abuse of notation, but that doing so has advantages. Inside an equation or inequality, the use of asymptotic notation stands for an anonymous function in the set
6011:." In another letter, Knuth also pointed out that "the equality sign is not symmetric with respect to such notations", as, in this notation, "mathematicians customarily use the = sign as they use the word "is" in English: Aristotle is a man, but a man isn't necessarily Aristotle".
2608:
13939:
So while all three statements are true, progressively more information is contained in each. In some fields, however, the big O notation (number 2 in the lists above) would be used more commonly than the big Theta notation (items numbered 3 in the lists above). For example, if
12524:
7571:
6770:)." In terms of the "set notation" above, the meaning is that the class of functions represented by the left side is a subset of the class of functions represented by the right side. In this use the "=" is a formal symbol that unlike the usual use of "=" is not a
525:
Big O notation characterizes functions according to their growth rates: different functions with the same asymptotic growth rate may be represented using the same O notation. The letter O is used because the growth rate of a function is also referred to as the
3350:{\displaystyle {\begin{aligned}e^{x}&=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb &{\text{for all }}x\\&=1+x+{\frac {x^{2}}{2}}+O(x^{3})&{\text{as }}x\to 0\\&=1+x+O(x^{2})&{\text{as }}x\to 0\end{aligned}}}
4692:
6450:
14080:
3558:
12154:
15773:(as well as the already mentioned other symbols) in his 1910 tract "Orders of Infinity", and made use of them only in three papers (1910–1913). In his nearly 400 remaining papers and books he consistently used the Landau symbols O and o.
3962:
13277:
11820:
11525:
12763:
13002:
3694:
Changing units may or may not affect the order of the resulting algorithm. Changing units is equivalent to multiplying the appropriate variable by a constant wherever it appears. For example, if an algorithm runs in the order of
2413:
8765:
5541:
9895:
1678:
13357:
14747:
741:
7947:
5129:
15951:
The big-O originally stands for "order of" ("Ordnung", Bachmann 1894), and is thus a Latin letter. Neither
Bachmann nor Landau ever call it "Omicron". The symbol was much later on (1976) viewed by Knuth as a capital
15004:
adopted it, and was thus inspired to introduce in 1909 the notation o; hence both are now called Landau symbols. These notations were used in applied mathematics during the 1950s for asymptotic analysis. The symbol
11892:
1596:
1297:
1071:
11306:, I feel justified in doing so because their definition is by no means in wide use, and because there are other ways to say what they want to say in the comparatively rare cases when their definition applies."
5592:
5454:
10382:
3089:
292:
13074:
12835:
10221:
5403:
11281:
12409:
3069:
in an approximation to a mathematical function. The most significant terms are written explicitly, and then the least-significant terms are summarized in a single big O term. Consider, for example, the
13952:, the inventors and users of the algorithm might be more inclined to put an upper asymptotic bound on how long it will take to run without making an explicit statement about the lower asymptotic bound.
8646:
12596:
11597:
9180:
93:
15180:, although it had been used before with different meanings, was given its modern definition by Landau in 1909 and by Hardy in 1910. Just above on the same page of his tract Hardy defined the symbol
4812:
3683:) and thus the big O notation ignores that. Similarly, logs with different constant bases are equivalent. On the other hand, exponentials with different bases are not of the same order. For example,
7440:
12234:
6455:
2418:
14062:
5245:
4984:
4206:
10546:
2769:
This distinction is only in application and not in principle, however—the formal definition for the "big O" is the same for both cases, only with different limits for the function argument.
2689:
1155:
11125:
2083:. In this setting, the contribution of the terms that grow "most quickly" will eventually make the other ones irrelevant. As a result, the following simplification rules can be applied:
1936:
1824:
942:
15631:
14555:
14498:
11188:-symbol to describe a stronger property. Knuth wrote: "For all the applications I have seen so far in computer science, a stronger requirement ... is much more appropriate". He defined
5019:
16658:
14920:
10606:
14315:
10865:
8249:
16557:
11036:
5597:
Under this definition, the subset on which a function is defined is significant when generalizing statements from the univariate setting to the multivariate setting. For example, if
3049:" is not meant to express "is equal to" in its normal mathematical sense, but rather a more colloquial "is", so the second expression is sometimes considered more accurate (see the "
17059:
15844:
15413:
15378:
13525:
10726:
10666:
10285:
10124:
13833:+ 58, all of the following are generally acceptable, but tighter bounds (such as numbers 2 and 3 below) are usually strongly preferred over looser bounds (such as number 1 below).
9391:
8403:
7636:
6851:, it is produced by simply typing O inside math mode. Unlike Greek-named Bachmann–Landau notations, it needs no special symbol. However, some authors use the calligraphic variant
1406:
15683:
8361:
10947:
9041:
4345:
15943:
15528:
13458:
13130:
12891:
12652:
11992:
9951:
9790:
9594:
6324:
4450:
10782:
8430:
6247:
4016:
2352:
1467:
15711:
5742:
4613:
3033:
15572:
15242:
13484:
11939:
8988:
7201:
6730:(·) on the right side, such that substituting all these functions into the equation makes the two sides equal. For example, the third equation above means: "For any function
5860:
5821:
4621:
7979:
7414:
7083:
6873:
4529:
4122:
4073:
2030:
15794:
15751:
12388:
11154:
11065:
10976:
10894:
10811:
9268:
8891:
7028:
2976:
15348:
15295:
12341:
12288:
11653:
11384:
10311:
10150:
10004:
9816:
9106:
6445:
5322:
4834:
119:
15135:
15108:
15081:
15054:
10497:
10470:
10443:
10416:
10061:
10034:
8816:
4923:
4867:
2063:
325:
13550:
8196:
4290:
4248:
13397:
8862:
7131:
15468:
15442:
9671:
8037:
7785:
7707:
7310:
7278:
6983:
6845:
5677:
5636:
3419:
16611:
15198:
15155:
15023:
13793:
13753:
13733:
13673:
13653:
13613:
13570:
12066:
11304:
11186:
9734:
9648:
9538:
9510:
5300:
5274:
1721:
1317:
231:
15814:
15771:
9620:
9472:
9437:
9341:
9306:
9227:
8302:
8275:
4741:
4485:
145:
16285:)) to express the same notion. You might be confused because we abuse equality in this way, but we shall see later in this section that doing so has its advantages.
15178:
14785:
13773:
12059:
12032:
8680:
8117:
6409:). Again, this usage disregards some of the formal meaning of the "=" symbol, but it does allow one to use the big O notation as a kind of convenient placeholder.
3826:
1983:
1601:
989:
198:
17127:
Gérald
Tenenbaum, Introduction to analytic and probabilistic number theory, « Notation », page xxiii. American Mathematical Society, Providence RI, 2015.
15868:
15731:
7351:
6940:
4374:
1496:
861:
832:
799:
770:
645:
16367:
13164:
11687:
8063:
7227:
1221:
171:
4890:
670:
15888:
13713:
13693:
13633:
13593:
13417:
13175:
11718:
11711:
11423:
11416:
5782:
5762:
4943:
4715:
4584:
4564:
1956:
1871:
1851:
1785:
1765:
1745:
1701:
1516:
1357:
1337:
1195:
1175:
1091:
962:
881:
665:
605:
577:
6707:{\displaystyle {\begin{aligned}(n+1)^{2}&=n^{2}+O(n),\\(n+O(n^{1/2}))\cdot (n+O(\log n))^{2}&=n^{3}+O(n^{5/2}),\\n^{O(1)}&=O(e^{n}).\end{aligned}}}
12671:
15137:("is not larger than a small o of"). Thus the Omega symbols (with their original meanings) are sometimes also referred to as "Landau symbols". This notation
14217:{\displaystyle O(g)=\{f:{\text{there exist positive constants}}~c~{\text{and}}~n_{0}~{\text{such that}}~0\leq f(n)\leq cg(n){\text{ for all }}n\geq n_{0}\}.}
12910:
1525:
1226:
994:
16040:
16809:
G. H. Hardy and J. E. Littlewood, « Contribution to the theory of the
Riemann zeta-function and the theory of the distribution of primes »,
8688:
5462:
9821:
13283:
5865:
This is not the only generalization of big O to multivariate functions, and in practice, there is some inconsistency in the choice of definition.
16495:
Donald E. Knuth, The art of computer programming. Vol. 1. Fundamental algorithms, third edition, Addison Wesley
Longman, 1997. Section 1.2.11.1.
14617:
17479:
7820:
5031:
16786:
15987:: A phrase frequently used to describe an algorithm that has an upper bound asymptotically within a constant of a lower bound for the problem
11826:
16451:
3629:. An algorithm can require time that is both superpolynomial and subexponential; examples of this include the fastest known algorithms for
1788:
17014:
17904:
5549:
5411:
2603:{\displaystyle {\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}}
16939:
13817:
bound where using big Theta Θ notation might be more factually appropriate in a given context. For example, when considering a function
10316:
236:
13008:
12769:
12519:{\displaystyle \forall \varepsilon >0\,\exists n_{0}\,\forall n>n_{0}\colon \left|{\frac {f(n)}{g(n)}}-1\right|<\varepsilon }
10155:
5330:
6889:
Here is a list of classes of functions that are commonly encountered when analyzing the running time of an algorithm. In each case,
437:
11194:
2613:
1096:
8446:
is widely used in computer science. Together with some other related notations, it forms the family of
Bachmann–Landau notations.
16824:
E. Landau, "Über die Anzahl der
Gitterpunkte in gewissen Bereichen. IV." Nachr. Gesell. Wiss. Gött. Math-phys. Kl. 1924, 137–150.
16121:
16015:
8583:
5971:
describes such statements as "one-way equalities", since if the sides could be reversed, "we could deduce ridiculous things like
12530:
11531:
9114:
3762:
in general. Changing variables may also affect the order of the resulting algorithm. For example, if an algorithm's run time is
16707:
16479:
16460:
16320:
37:
17150:
7566:{\displaystyle \log ^{*}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{cases}}}
4746:
17743:
17713:
17677:
17611:
17513:
17330:
17200:
16985:
16734:
16415:
16361:
16206:
16851:, Introduction to analytic and probabilistic number theory, Chapter I.5. American Mathematical Society, Providence RI, 2015.
16421:
6421:(·) can appear in different places in an equation, even several times on each side. For example, the following are true for
15350:
are satisfied. The notation is still currently used in analytic number theory. In his tract Hardy also proposed the symbol
6139:
Big O notation can also be used in conjunction with other arithmetic operators in more complicated equations. For example,
16765:"Some problems of diophantine approximation: Part II. The trigonometrical series associated with the elliptic θ-functions"
12158:
15973:
13992:
16351:
7721:
5925:, since the use of the equals sign could be misleading as it suggests a symmetry that this statement does not have. As
5148:
2302:
1412:
6050:
4948:
4127:
17437:
17109:
16009:
10505:
15984:
7434:
6884:
2167:. Of these three terms, the one with the highest growth rate is the one with the largest exponent as a function of
11076:
1880:
1794:
886:
17938:
9697:
3066:
2854:
term. Ignoring the latter would have negligible effect on the expression's value for most purposes. Further, the
507:
15587:
14578:"nitpicking" within growth-rates that are stated as too tightly bounded for the matters at hand (since log
14503:
14442:
4989:
17928:
16616:
14864:
10551:
7237:
15029:
of") was introduced in 1914 by Hardy and
Littlewood. Hardy and Littlewood also introduced in 1916 the symbols
14241:
10822:
8201:
17414:). Using asymptotic notation in this manner can help eliminate inessential detail and clutter in an equation.
16520:
15990:
10987:
3071:
474:
430:
17338:
interpret it as standing for some anonymous function that we do not care to name. For example, the formula 2
15819:
15383:
15353:
13814:
13489:
10671:
10611:
10230:
10069:
2098:
is a sum of several terms, if there is one with largest growth rate, it can be kept, and all others omitted.
17933:
17891:
9346:
8366:
7579:
1363:
360:
16066:
15636:
14235:), which eliminates lower-order terms, and helps to reduce inessential clutter in equations, for example:
8308:
518:
and a better understood approximation; a famous example of such a difference is the remainder term in the
16684:
16150:
15847:
10905:
8994:
8127:
8073:
7038:
4295:
15896:
15480:
13422:
13082:
12843:
12604:
11944:
9903:
9742:
9546:
6258:
4687:{\displaystyle f(\mathbf {x} ){\text{ is }}O(g(\mathbf {x} ))\quad {\text{ as }}\mathbf {x} \to \infty }
4395:
3402:
can be written as a finite sum of other functions, then the fastest growing one determines the order of
17703:
17657:
17572:
17099:
13962:
10746:
8409:
7997:
7032:
6184:
3968:
15691:
5682:
4589:
2987:
2797:
for efficiency. For example, the time (or the number of steps) it takes to complete a problem of size
17462:
17454:
17427:
15533:
15203:
13463:
11900:
8941:
7158:
5926:
5826:
5787:
1827:
1787:
there have to be infinitely many points in common. Moreover, as pointed out in the article about the
17034:
10391:, with the same meanings, in 1924. After Landau, the notations were never used again exactly thus;
7474:
7374:
7047:
6854:
4490:
4078:
4029:
1988:
17735:
15779:
15736:
14570:
14381:
12349:
11130:
11041:
10952:
10870:
10787:
9232:
8867:
7952:
6995:
6370:
steps before it terminates. Thus the overall time complexity of the algorithm can be expressed as
2930:
423:
17322:
16300:
16198:
15300:
15247:
14757:
12293:
12240:
11605:
11336:
10290:
10129:
9956:
9795:
9058:
6424:
5305:
4817:
2781:
Graphs of functions commonly used in the analysis of algorithms, showing the number of operations
2749:
is typically chosen to be as simple as possible, omitting constant factors and lower order terms.
98:
16764:
15113:
15086:
15059:
15032:
14753:
10475:
10448:
10421:
10394:
10039:
10012:
9713:
8776:
7799:
7141:
4895:
4839:
3553:{\displaystyle f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{as }}n\to \infty .}
2859:
2035:
297:
13529:
12149:{\displaystyle \exists k_{1}>0\,\exists k_{2}>0\,\exists n_{0}\,\forall n>n_{0}\colon }
8154:
4253:
4211:
17029:
16035:
14997:
13804:
13367:
10729:
9693:
8821:
7795:
7655:
7101:
2794:
511:
496:
466:
462:
355:
17901:
16965:
15447:
15418:
9653:
8006:
7754:
7676:
7247:
6952:
6814:
5641:
5600:
3957:{\displaystyle f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})}
16916:
16578:
15183:
15140:
15008:
13778:
13738:
13718:
13658:
13638:
13598:
13555:
11289:
11171:
9719:
9633:
9523:
9477:
8131:
7430:
7283:
5279:
5253:
3630:
2112:
is a product of several factors, any constants (factors in the product that do not depend on
1706:
1302:
203:
17727:
17314:
16190:
15799:
15756:
9599:
9442:
9407:
9311:
9276:
9197:
8281:
8254:
4720:
4455:
607:, the comparison function, be a real valued function. Let both functions be defined on some
124:
17691:
17087:
16021:
15978:
15163:
14926:
14764:
14335:), which hides polylogarithmic factors. There are two definitions in use: some authors use
13971:
13758:
12037:
12010:
9709:
9540:, read "big omega". There are two widespread and incompatible definitions of the statement
8658:
8090:
7987:
7231:
7091:
2715:
1961:
1073:
In many contexts, the assumption that we are interested in the growth rate as the variable
967:
519:
411:
401:
176:
17:
15853:
15716:
13272:{\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon |f(n)|\geq k\,g(n)}
11815:{\displaystyle \exists k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\,g(n)}
11520:{\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\,g(n)}
7327:
6916:
4350:
3605:
is greater than one, then the latter grows much faster. A function that grows faster than
1472:
837:
808:
775:
746:
621:
8:
17902:
An example of Big O in accuracy of central divided difference scheme for first derivative
17797:
17728:
17651:
17599:
17566:
17542:
17528:
E. C. Titchmarsh, The Theory of the
Riemann Zeta-Function (Oxford; Clarendon Press, 1951)
17315:
16924:
RAIRO – Theoretical
Informatics and Applications – Informatique Théorique et Applications
16191:
16093:
14797:
14574:
13139:
12402:
11662:
9397:
8077:
7145:
1200:
515:
458:
380:
150:
16848:
12758:{\displaystyle \exists k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)\geq k\,g(n)}
8042:
7206:
4872:
510:
according to how their run time or space requirements grow as the input size grows. In
17452:
17312:
17190:
17049:
16895:
16188:
16029:
15873:
13698:
13678:
13618:
13578:
13402:
12997:{\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)>k\,g(n)}
11696:
11401:
8081:
7365:
6771:
5767:
5747:
4928:
4700:
4569:
4549:
1941:
1856:
1836:
1770:
1750:
1730:
1686:
1501:
1342:
1322:
1180:
1160:
1076:
947:
866:
650:
590:
562:
17818:
17776:
16836:
16114:
15846:) are not used anymore. On the other hand, in the 1930s, the Russian number theorist
14439:, there is no difference; however, the latter definition allows one to say, e.g. that
2777:
17739:
17709:
17673:
17607:
17595:
17509:
17433:
17426:
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022).
17326:
17207:
When we have only an asymptotic upper bound, we use O-notation. For a given function
17196:
17105:
16981:
16931:
16740:
16730:
16411:
16357:
16202:
14855:
14836:
14813:
8139:
7640:
5922:
3054:
340:
17754:
17054:
16704:
16476:
16443:
16313:
17763:
17695:
17687:
17471:
17139:
17083:
17039:
17010:
16973:
16900:
16885:
16811:
16776:
16025:
15574:, and proposed a different definition for the Hardy and Littlewood Omega notation.
13975:
13967:
8067:
7811:
7135:
2721:
530:. A description of a function in terms of big O notation usually only provides an
503:
6897:
increases without bound. The slower-growing functions are generally listed first.
2833:
will come to dominate, so that all other terms can be neglected—for instance when
17908:
17767:
16711:
16483:
16405:
16347:
7993:
7803:
7789:
7659:
2752:
There are two formally close, but noticeably different, usages of this notation:
1874:
522:. Big O notation is also used in many other fields to provide similar estimates.
491:
375:
11286:
with the comment: "Although I have changed Hardy and
Littlewood's definition of
4542:(and little o, Ω, etc.) can also be used with multiple variables. To define big
537:
Associated with big O notation are several related notations, using the symbols
17860:
17839:
17723:
17699:
17672:. The Art of Computer Programming. Vol. 1 (3rd ed.). Addison-Wesley.
17095:
16401:
13979:
9055:) is nonzero, or at least becomes nonzero beyond a certain point, the relation
8760:{\displaystyle |f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x_{0}.}
7733:
7729:
7711:
5536:{\displaystyle \forall m\colon ~f(n,m)=O(n^{m})\quad {\text{ as }}n\to \infty }
5022:
1519:
802:
584:
514:, big O notation is often used to express a bound on the difference between an
16977:
9890:{\displaystyle \limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|>0.}
8561:
a real valued function, both defined on some unbounded subset of the positive
6811:
Big O is typeset as an italicized uppercase "O", as in the following example:
1673:{\displaystyle \limsup _{x\to a}{\frac {\left|f(x)\right|}{g(x)}}<\infty .}
17922:
17538:
16935:
16744:
16680:
16393:
16146:
16089:
16062:
15001:
14989:
14983:
13352:{\displaystyle \limsup _{n\to \infty }{\frac {\left|f(n)\right|}{g(n)}}>0}
10388:
7149:
6944:
2762:
2711:
1724:
478:
406:
396:
370:
16890:
16873:
16018:: For analyzing divide-and-conquer recursive algorithms using Big O notation
14808:
need not take their values in the same space. A generalization to functions
13948:) represents the running time of a newly developed algorithm for input size
17896:
17665:
17603:
17587:
17006:
16397:
15474:
14858:
in quite general spaces, and also (asymptotical) equivalence of functions,
14742:{\displaystyle L_{n}=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }},}
13419:. The table is (partly) sorted from smallest to largest, in the sense that
11165:
8900:
and the definition of little-o is that while the former has to be true for
8455:
6986:
6015:
5968:
736:{\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to \infty }
17887:
Growth of sequences — OEIS (Online Encyclopedia of Integer Sequences) Wiki
17044:
16724:
13813:
notation often can be used somewhat differently to describe an asymptotic
9182:(and this is in fact how Landau originally defined the little-o notation).
8922:
than the corresponding big-O notation: every function that is little-o of
7942:{\displaystyle L_{n}=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}
5124:{\displaystyle f(n,m)=n^{2}+m^{3}+O(n+m)\quad {\text{ as }}n,m\to \infty }
17647:
17562:
14832:
8562:
8143:
8135:
7807:
7725:
7355:
4377:
2855:
2703:
1681:
615:
608:
580:
531:
7360:
Finding an item in an unsorted list or in an unsorted array; adding two
3619:. One that grows more slowly than any exponential function of the form
17091:
16781:
16559:
Fast Direct Solver for Partial Hierarchically Semi-Separable Matrices,
14851:
14605:
7983:
7736:; (worst-case) bound on some usually faster sorting algorithms such as
7667:
6358:), and after the subroutine runs the algorithm must take an additional
1833:
In computer science, a slightly more restrictive definition is common:
17886:
17475:
14565:
for the same purpose as the latter definition. Essentially, it is big
11887:{\displaystyle \limsup _{n\to \infty }{\frac {f(n)}{g(n)}}<\infty }
8130:
via brute-force search; generating all unrestricted permutations of a
15870:, which has been increasingly used in number theory instead of the
14356:
8121:
7745:
7741:
7737:
6335:
1591:{\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to a}
1292:{\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\quad {\text{ as }}x\to a}
469:
tends towards a particular value or infinity. Big O is a member of a
17313:
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (2009).
17191:
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (2009).
16189:
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (2009).
6949:
Finding the median value for a sorted array of numbers; Calculating
2243:. One may confirm this calculation using the formal definition: let
1873:
are both required to be functions from some unbounded subset of the
1066:{\displaystyle |f(x)|\leq Mg(x)\quad {\text{ for all }}x\geq x_{0}.}
16917:"Nonuniform complexity classes specified by lower and upper bounds"
16839:. The Riemann zeta-function, chapter 9. John Wiley & Sons 1985.
16410:(2 ed.). Reading, Massachusetts: Addison–Wesley. p. 446.
16012:: An explanation of some of the limit notation used in this article
15733:, as it has been sometimes reported). Hardy introduced the symbols
9186:
Little-o respects a number of arithmetic operations. For example,
7663:
7421:
7318:
5587:{\displaystyle \forall m\,\exists C\,\exists M\,\forall n\,\cdots }
5449:{\displaystyle \exists C\,\exists M\,\forall n\,\forall m\,\cdots }
2756:
1093:
goes to infinity is left unstated, and one writes more simply that
17913:
16115:"Quantum Computing in Complexity Theory and Theory of Computation"
17653:
Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond
17568:
Orders of Infinity: The 'Infinitärcalcül' of Paul du Bois-Reymond
17432:(4th ed.). Cambridge, Mass.: The MIT Press. pp. 74–75.
16506:
Concrete Mathematics: A Foundation for Computer Science (2nd ed.)
15953:
10377:{\displaystyle \liminf _{x\to \infty }{\frac {f(x)}{g(x)}}<0.}
7236:
Matrix chain ordering can be solved in polylogarithmic time on a
2830:
287:{\displaystyle 0\leq {\color {red}f(x)}\leq M{\color {blue}g(x)}}
30:
17453:
Andreas Björklund and Thore Husfeldt and Mikko Koivisto (2009).
17149:. Math 595, Fall 2009. Urbana, IL: University of Illinois.
15157:
became commonly used in number theory at least since the 1950s.
13069:{\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=\infty }
12830:{\displaystyle \liminf _{n\to \infty }{\frac {f(n)}{g(n)}}>0}
10216:{\displaystyle \limsup _{x\to \infty }{\frac {f(x)}{g(x)}}>0}
5398:{\displaystyle f(n,m)=O(n^{m})\quad {\text{ as }}n,m\to \infty }
3053:" discussion below) while the first is considered by some as an
551:, to describe other kinds of bounds on asymptotic growth rates.
15577:
Two other symbols coined by Hardy were (in terms of the modern
14800:
is straightforward (replacing absolute values by norms), where
3563:
In particular, if a function may be bounded by a polynomial in
611:
15473:
In the 1970s the big O was popularized in computer science by
14320:
11276:{\displaystyle f(x)=\Omega (g(x))\Leftrightarrow g(x)=O(f(x))}
8251:
to derive simpler formulas for asymptotic complexity. For any
6342:
elements. Its developers are interested in finding a function
2149:
approaches infinity. This function is the sum of three terms:
15957:
8434:
so may be considered as a polynomial with some bigger order.
8080:; determining if two logical statements are equivalent using
17181:-notation where the Θ-notation is more technically precise."
14067:
In a correct notation this set can, for instance, be called
17104:(2nd ed.). MIT Press and McGraw-Hill. pp. 41–50.
8641:{\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to \infty }
7559:
2079:
notation is asymptotical, that is, it refers to very large
17686:
17425:
17174:
17082:
16722:
16697:
16296:
15981:: Approximation of functions generalizing Taylor's formula
15948:
and frequently both notations are used in the same paper.
14984:
History (Bachmann–Landau, Hardy, and Vinogradov notations)
14327:
12591:{\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1}
11592:{\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0}
9175:{\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0}
7090:
Average number of comparisons spent finding an item using
1157:
The notation can also be used to describe the behavior of
17859:
Black, Paul E. (17 December 2004). Black, Paul E. (ed.).
17838:
Black, Paul E. (17 December 2004). Black, Paul E. (ed.).
17817:
Black, Paul E. (17 December 2004). Black, Paul E. (ed.).
17796:
Black, Paul E. (17 December 2004). Black, Paul E. (ed.).
17762:. International Joint Conference on Automated Reasoning.
16729:(3rd ed.). Cambridge, Mass.: MIT Press. p. 48.
6848:
6162:
denotes the collection of functions having the growth of
5302:
holds. This definition allows all of the coordinates of
3668:. The logarithms differ only by a constant factor (since
2708:
how closely a finite series approximates a given function
88:{\displaystyle {\color {red}f(x)}=O{\color {blue}(g(x))}}
17549:
Handbook on the theory of the distribution of the primes
16691:
Handbook on the theory of the distribution of the primes
16157:
Handbook on the theory of the distribution of the primes
16100:
Handbook on the theory of the distribution of the primes
15956:, probably in reference to his definition of the symbol
13572:, however, doesn't correspond to any such description).
10009:
In 1916 the same authors introduced the two new symbols
8918:, however small. In this way, little-o notation makes a
8454:"Little o" redirects here. For the baseball player, see
6885:
Time complexity § Table of common time complexities
4807:{\displaystyle |f(\mathbf {x} )|\leq C|g(\mathbf {x} )|}
16504:
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik,
16388:
16386:
16384:
16102:] (in German). Leipzig: B. G. Teubner. p. 883.
14325:
Another notation sometimes used in computer science is
2862:
of expression, such as an expression containing a term
2139:, and suppose we wish to simplify this function, using
17914:
A Gentle Introduction to Algorithm Complexity Analysis
17775:
Black, Paul E. (11 March 2005). Black, Paul E. (ed.).
17551:] (in German). Leipzig: B. G. Teubner. p. 62.
16693:] (in German). Leipzig: B. G. Teubner. p. 61.
16508:, Addison-Wesley, 1994. Section 9.2, p. 443.
11309:
8573:) is strictly positive for all large enough values of
8045:
7955:
7286:
7209:
5324:
to increase to infinity. In particular, the statement
2201:. Omitting this factor results in the simplified form
1798:
17867:. U.S. National Institute of Standards and Technology
17846:. U.S. National Institute of Standards and Technology
17825:. U.S. National Institute of Standards and Technology
17804:. U.S. National Institute of Standards and Technology
17783:. U.S. National Institute of Standards and Technology
17195:(3rd ed.). Cambridge/MA: MIT Press. p. 47.
16619:
16581:
16523:
16159:] (in German). Leipzig: B.G. Teubner. p. 31.
15961:
15899:
15876:
15856:
15822:
15802:
15782:
15759:
15739:
15719:
15694:
15639:
15590:
15536:
15483:
15450:
15421:
15386:
15356:
15303:
15250:
15206:
15186:
15166:
15143:
15116:
15089:
15062:
15035:
15011:
14988:
The symbol O was first introduced by number theorist
14929:
and a more restrictive notion than the relationship "
14867:
14796:
The generalization to functions taking values in any
14791:
14767:
14620:
14506:
14445:
14244:
14083:
13995:
13781:
13761:
13741:
13721:
13701:
13681:
13675:
notations. Analytic number theory often uses the big
13661:
13641:
13621:
13601:
13581:
13558:
13532:
13492:
13466:
13425:
13405:
13370:
13286:
13178:
13142:
13085:
13011:
12913:
12846:
12772:
12674:
12607:
12533:
12412:
12352:
12296:
12243:
12161:
12069:
12040:
12013:
11947:
11903:
11829:
11721:
11699:
11665:
11608:
11534:
11426:
11404:
11339:
11292:
11197:
11174:
11133:
11079:
11044:
10990:
10955:
10908:
10873:
10825:
10790:
10749:
10674:
10614:
10554:
10508:
10478:
10451:
10424:
10397:
10319:
10293:
10233:
10158:
10132:
10072:
10042:
10015:
9959:
9906:
9824:
9798:
9745:
9722:
9656:
9636:
9602:
9549:
9526:
9480:
9445:
9410:
9349:
9314:
9279:
9235:
9200:
9117:
9061:
8997:
8944:
8870:
8824:
8779:
8691:
8661:
8586:
8412:
8369:
8311:
8284:
8257:
8204:
8157:
8093:
8009:
7823:
7757:
7679:
7582:
7443:
7377:
7330:
7250:
7161:
7104:
7050:
6998:
6955:
6919:
6857:
6817:
6453:
6427:
6261:
6187:
5829:
5790:
5770:
5750:
5685:
5644:
5603:
5552:
5465:
5414:
5333:
5308:
5282:
5256:
5151:
5034:
4992:
4951:
4931:
4898:
4875:
4842:
4820:
4749:
4723:
4703:
4624:
4592:
4572:
4552:
4493:
4458:
4398:
4353:
4298:
4256:
4214:
4130:
4081:
4032:
3971:
3829:
3422:
3087:
2990:
2933:
2616:
2416:
2305:
2038:
1991:
1964:
1944:
1883:
1859:
1839:
1797:
1773:
1753:
1733:
1709:
1689:
1604:
1528:
1518:, both of these definitions can be unified using the
1504:
1498:
is chosen to be strictly positive for such values of
1475:
1415:
1366:
1345:
1325:
1305:
1229:
1203:
1183:
1163:
1099:
1079:
997:
970:
950:
889:
869:
840:
811:
778:
749:
673:
653:
624:
593:
565:
300:
239:
206:
179:
153:
127:
101:
40:
17544:
Handbuch der Lehre von der Verteilung der Primzahlen
16723:
Cormen TH, Leiserson CE, Rivest RL, Stein C (2009).
16686:
Handbuch der Lehre von der Verteilung der Primzahlen
16392:
16381:
16152:
Handbuch der Lehre von der Verteilung der Primzahlen
16095:
Handbuch der Lehre von der Verteilung der Primzahlen
14953:
are positive real valued functions.) For example, 2
14831:
can also be generalized by introducing an arbitrary
13894:
The equivalent English statements are respectively:
13809:
Informally, especially in computer science, the big
12229:{\displaystyle k_{1}\,g(n)\leq f(n)\leq k_{2}\,g(n)}
6131:. However, the use of the equals sign is customary.
647:
be strictly positive for all large enough values of
489:. The letter O was chosen by Bachmann to stand for
16705:
Introduction to Algorithms, Second Edition, Ch. 3.1
16041:
Computational complexity of mathematical operations
6014:For these reasons, it would be more precise to use
4347:. In other words, this second statement says that
16972:. Berlin, Heidelberg: Springer. pp. 467–468.
16652:
16605:
16551:
15937:
15882:
15862:
15838:
15808:
15788:
15765:
15745:
15725:
15705:
15688:(Hardy however never defined or used the notation
15677:
15625:
15566:
15522:
15462:
15436:
15407:
15372:
15342:
15289:
15236:
15192:
15172:
15149:
15129:
15102:
15075:
15048:
15017:
14914:
14779:
14741:
14549:
14492:
14309:
14216:
14057:{\displaystyle f(n)=O(g(n))\quad (n\to \infty )~.}
14056:
13787:
13767:
13747:
13727:
13707:
13687:
13667:
13647:
13627:
13607:
13587:
13564:
13552:on the real line (the Hardy–Littlewood version of
13544:
13519:
13478:
13452:
13411:
13391:
13351:
13271:
13158:
13124:
13068:
12996:
12885:
12829:
12757:
12646:
12590:
12518:
12382:
12335:
12282:
12228:
12148:
12053:
12026:
11986:
11933:
11886:
11814:
11705:
11681:
11647:
11591:
11519:
11410:
11378:
11298:
11275:
11180:
11148:
11119:
11059:
11030:
10970:
10941:
10888:
10859:
10805:
10776:
10720:
10660:
10600:
10540:
10491:
10464:
10437:
10410:
10376:
10305:
10279:
10215:
10144:
10118:
10055:
10028:
9998:
9945:
9889:
9810:
9784:
9728:
9703:
9692:The Hardy–Littlewood definition is used mainly in
9665:
9642:
9614:
9588:
9532:
9504:
9466:
9431:
9385:
9335:
9300:
9262:
9221:
9174:
9100:
9035:
8982:
8885:
8856:
8810:
8759:
8674:
8640:
8424:
8397:
8355:
8296:
8269:
8243:
8190:
8111:
8057:
8031:
7973:
7941:
7779:
7701:
7630:
7565:
7408:
7345:
7304:
7272:
7221:
7195:
7125:
7094:in a sorted array of uniformly distributed values
7077:
7022:
6977:
6934:
6867:
6839:
6714:The meaning of such statements is as follows: for
6706:
6439:
6318:
6241:
5854:
5815:
5776:
5756:
5736:
5671:
5630:
5586:
5535:
5448:
5397:
5316:
5294:
5268:
5239:
5123:
5013:
4978:
4937:
4917:
4884:
4861:
4828:
4806:
4735:
4709:
4686:
4607:
4578:
4558:
4523:
4479:
4444:
4368:
4339:
4284:
4242:
4200:
4116:
4067:
4010:
3956:
3552:
3349:
3027:
2970:
2698:Big O notation has two main areas of application:
2683:
2602:
2346:
2057:
2024:
1977:
1950:
1930:
1865:
1845:
1818:
1779:
1759:
1739:
1715:
1695:
1672:
1590:
1510:
1490:
1461:
1400:
1351:
1331:
1311:
1291:
1215:
1189:
1169:
1149:
1085:
1065:
983:
956:
936:
875:
855:
826:
793:
764:
735:
659:
639:
599:
571:
319:
286:
225:
192:
165:
139:
113:
87:
17606:(6th ed.). Oxford: Oxford University Press.
17321:(3rd ed.). Cambridge/MA: MIT Press. p.
16197:(3rd ed.). Cambridge/MA: MIT Press. p.
16075:] (in German). Vol. 2. Leipzig: Teubner.
15832:
15831:
15830:
15829:
15828:
15827:
15699:
15698:
15398:
15397:
15396:
15395:
15394:
15393:
15366:
15365:
15364:
15363:
15362:
15361:
9681:are real functions defined in a neighbourhood of
6170:) plus a part whose growth is limited to that of
5240:{\displaystyle |f(n,m)-(n^{2}+m^{3})|\leq C|n+m|}
3740:. If, however, an algorithm runs in the order of
470:
17920:
16314:"On Asymptotic Notation with Multiple Variables"
16106:
13288:
13013:
12774:
12535:
11997:Of the same order as (Hardy); Big Theta (Knuth)
11831:
11536:
10321:
10160:
9826:
9119:
4979:{\displaystyle \|\mathbf {x} \|_{\infty }\geq M}
4201:{\displaystyle f_{1}+f_{2}=O(\max(g_{1},g_{2}))}
4163:
3796:when measured as a function of the input number
2902:, the latter will always exceed the former once
1800:
1606:
17005:
16970:Condition: The Geometry of Numerical Algorithms
16963:
16762:
16675:
16673:
16346:
16028:functions so that the domain of convergence of
13755:(with or without the +, − or ± subscripts) and
10728:are both satisfied), are now currently used in
10541:{\displaystyle \Omega ,\Omega _{+},\Omega _{-}}
8437:
4383:
17752:
17668:(1997). "1.2.11: Asymptotic Representations".
16966:"A.1 Big Oh, Little Oh, and Other Comparisons"
16169:
13134:Big Omega in number theory (Hardy–Littlewood)
3720:, and the big O notation ignores the constant
3074:and two expressions of it that are valid when
2707:
2684:{\displaystyle |6x^{4}-2x^{3}+5|\leq 13x^{4}.}
457:is a mathematical notation that describes the
14752:is convenient for functions that are between
6878:
6134:
2858:become irrelevant if we compare to any other
2195:in which the first factor does not depend on
1923:
1904:
1568:
1549:
1269:
1250:
1150:{\displaystyle f(x)=O{\bigl (}g(x){\bigr )}.}
1139:
1120:
929:
910:
713:
694:
431:
17865:Dictionary of Algorithms and Data Structures
17844:Dictionary of Algorithms and Data Structures
17823:Dictionary of Algorithms and Data Structures
17802:Dictionary of Algorithms and Data Structures
17781:Dictionary of Algorithms and Data Structures
16670:
16498:
16452:Notices of the American Mathematical Society
16441:
15083:("left"), precursors of the modern symbols
14208:
14099:
11168:published a paper to justify his use of the
11120:{\displaystyle \sin x+1\not =\Omega _{-}(1)}
5002:
4993:
4961:
4952:
4586:are two functions defined on some subset of
3060:
1931:{\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}
1819:{\displaystyle \textstyle \limsup _{x\to a}}
937:{\displaystyle f(x)=O{\bigl (}g(x){\bigr )}}
17708:(2nd ed.). MIT Press and McGraw-Hill.
17585:
16914:
14321:Extensions to the Bachmann–Landau notations
13795:notation is not used as often in analysis.
7037:Amortized complexity per operation for the
5898:))" as defined above is usually written as
834:is at most a positive constant multiple of
17522:
17455:"Set partitioning via inclusion-exclusion"
17177:, p. 64: "Many people continue to use the
16356:. Amsterdam: North-Holland. pp. 5–7.
16342:
16340:
16057:
16055:
15913:
15909:
15653:
15649:
15626:{\displaystyle f\preccurlyeq g\iff f=O(g)}
15604:
15600:
14992:in 1894, in the second volume of his book
14881:
14877:
14550:{\displaystyle \log ^{k}n={\tilde {O}}(1)}
14493:{\displaystyle n2^{n}={\tilde {O}}(2^{n})}
13798:
8930:, but not every function that is big-O of
6338:is being developed to operate on a set of
5014:{\displaystyle \|\mathbf {x} \|_{\infty }}
2354:for some suitable choice of a real number
438:
424:
17730:Introduction to the Theory of Computation
17053:
17043:
17033:
16964:Cucker, Felipe; Bürgisser, Peter (2013).
16899:
16889:
16874:"Big Omicron and big Omega and big Theta"
16780:
16660:-Time Algorithm and a Polynomial Kernel,
16653:{\displaystyle {\mathcal {O}}^{*}(2^{p})}
16172:Introduction to the Theory of Computation
15823:
15357:
15110:("is not smaller than a small o of") and
14915:{\displaystyle f\sim g\iff (f-g)\in o(g)}
14816:is also possible. The "limiting process"
13256:
13205:
13191:
12981:
12940:
12926:
12742:
12701:
12687:
12439:
12425:
12213:
12172:
12123:
12109:
12089:
11799:
11748:
11734:
11504:
11453:
11439:
10601:{\displaystyle f(x)=\Omega _{\pm }(g(x))}
8557:be a real or complex valued function and
7140:Finding an item in a sorted array with a
5580:
5573:
5566:
5559:
5442:
5435:
5428:
5421:
4595:
4546:formally for multiple variables, suppose
3711:means the algorithm runs in the order of
3368:)) means the absolute-value of the error
2725:
2145:notation, to describe its growth rate as
27:Describes limiting behavior of a function
17753:Avigad, Jeremy; Donnelly, Kevin (2004).
17592:An Introduction to the Theory of Numbers
17263:) : there exist positive constants
16908:
16867:
16865:
16863:
16861:
16859:
16857:
16763:Hardy, G. H.; Littlewood, J. E. (1914).
16489:
16084:
16082:
16061:
14310:{\displaystyle 2n^{2}+3n+1=2n^{2}+O(n).}
11398:asymptotically (for any constant factor
10860:{\displaystyle \sin x=\Omega _{\pm }(1)}
8244:{\displaystyle f(n)=O\left(n^{n}\right)}
2776:
2710:, especially in the case of a truncated
1938:if there exist positive integer numbers
1767:, i. e., in every neighbourhood of
29:
17503:
17001:
16999:
16997:
16832:
16830:
16552:{\displaystyle {\mathcal {O}}(N\log N)}
16517:Sivaram Ambikasaran and Eric Darve, An
16337:
16184:
16182:
16052:
16046:
16016:Master theorem (analysis of algorithms)
14500:while the former definition allows for
14393:, while others use it as shorthand for
12656:Big Omega in complexity theory (Knuth)
11388:Small O; Small Oh; Little O; Little Oh
11159:
11031:{\displaystyle \sin x+1=\Omega _{+}(1)}
6401:are subsumed within the faster-growing
3065:Big O can also be used to describe the
2772:
944:if there exists a positive real number
14:
17921:
17756:Formalizing O notation in Isabelle/HOL
17722:
17537:
17137:
16957:
16818:
16805:
16803:
16679:
16145:
16139:
16088:
15839:{\displaystyle \,\asymp \!\!\!\!\!\!-}
15477:, who proposed the different notation
15408:{\displaystyle f\asymp \!\!\!\!\!\!-g}
15373:{\displaystyle \,\asymp \!\!\!\!\!\!-}
13918:) grows asymptotically no faster than
13905:) grows asymptotically no faster than
13520:{\displaystyle <,\leq ,\approx ,=,}
10721:{\displaystyle f(x)=\Omega _{-}(g(x))}
10661:{\displaystyle f(x)=\Omega _{+}(g(x))}
10280:{\displaystyle f(x)=\Omega _{L}(g(x))}
10119:{\displaystyle f(x)=\Omega _{R}(g(x))}
9700:; the definitions are not equivalent.
8897:
5868:
2277:
1877:to the nonnegative real numbers; then
17858:
17837:
17816:
17795:
17774:
17664:
17646:
17626:See for instance "A new estimate for
17561:
17555:
17123:
17121:
17015:"Big Omega versus the wild functions"
16915:Balcázar, José L.; Gabarró, Joaquim.
16871:
16854:
16758:
16756:
16754:
16079:
9696:, and the Knuth definition mainly in
9515:
9386:{\displaystyle f\cdot g=o(F\cdot G).}
8398:{\displaystyle O(n^{c+\varepsilon })}
7724:; simple sorting algorithms, such as
7631:{\displaystyle O(n\log n)=O(\log n!)}
4697:if and only if there exist constants
4533:
3773:when measured in terms of the number
2178:. Now one may apply the second rule:
1680:And in both of these definitions the
1401:{\displaystyle 0<|x-a|<\delta }
863:for all sufficiently large values of
579:, the function to be estimated, be a
17897:Big-O Notation – What is it good for
17892:Introduction to Asymptotic Notations
17702:(2001). "3.1: Asymptotic notation".
16994:
16827:
16179:
15678:{\displaystyle f\prec g\iff f=o(g);}
8449:
8356:{\displaystyle O(n^{c}(\log n)^{k})}
8072:Finding the (exact) solution to the
3380:/2) is at most some constant times |
3360:The middle expression (the one with
554:
534:on the growth rate of the function.
16800:
16265:)). Instead, we will usually write
15974:Asymptotic computational complexity
11689:is asymptotically bounded above by
11310:Family of Bachmann–Landau notations
10942:{\displaystyle \sin x+1=\Omega (1)}
9689:is positive in this neighbourhood.
9036:{\displaystyle 2x^{2}\neq o(x^{2})}
6789:does not imply the false statement
5134:asserts that there exist constants
4340:{\displaystyle f_{1}+f_{2}\in O(g)}
2731:In both applications, the function
24:
17640:
17156:from the original on 14 March 2017
17118:
16945:from the original on 14 March 2017
16751:
16623:
16526:
16311:
15938:{\displaystyle f\ll g\iff f=O(g),}
15523:{\displaystyle f(x)=\Theta (g(x))}
15499:
15144:
15118:
15091:
15064:
15037:
15012:
14937:)" from above. (It reduces to lim
14792:Generalizations and related usages
14042:
13931:) grows asymptotically as fast as
13742:
13662:
13602:
13559:
13467:
13453:{\displaystyle o,O,\Theta ,\sim ,}
13438:
13298:
13206:
13192:
13179:
13125:{\displaystyle f(n)=\Omega (g(n))}
13101:
13063:
13023:
12941:
12927:
12914:
12886:{\displaystyle f(n)=\omega (g(n))}
12784:
12702:
12688:
12675:
12647:{\displaystyle f(n)=\Omega (g(n))}
12623:
12545:
12440:
12426:
12413:
12124:
12110:
12090:
12070:
12034:) and below (with constant factor
11987:{\displaystyle f(n)=\Theta (g(n))}
11963:
11881:
11841:
11749:
11735:
11722:
11546:
11454:
11440:
11427:
11293:
11213:
11175:
11140:
11099:
11051:
11010:
10962:
10927:
10880:
10839:
10797:
10762:
10735:
10691:
10631:
10571:
10529:
10516:
10509:
10480:
10453:
10426:
10399:
10331:
10300:
10250:
10170:
10139:
10089:
10044:
10017:
9946:{\displaystyle f(x)=\Omega (g(x))}
9922:
9836:
9805:
9785:{\displaystyle f(x)=\Omega (g(x))}
9761:
9723:
9660:
9637:
9589:{\displaystyle f(x)=\Omega (g(x))}
9565:
9527:
9129:
8877:
8635:
6860:
6434:
6319:{\displaystyle g(x)-h(x)=O(f(x)).}
5839:
5800:
5574:
5567:
5560:
5553:
5530:
5466:
5436:
5429:
5422:
5415:
5392:
5118:
5006:
4965:
4681:
4445:{\displaystyle O(|k|\cdot g)=O(g)}
3646:inside of the logarithms. The set
3579:terms of the polynomial. The sets
3544:
2706:, it is commonly used to describe
1710:
1664:
730:
481:, and others, collectively called
473:invented by German mathematicians
269:
108:
64:
25:
17950:
17880:
16872:Knuth, Donald (April–June 1976).
16575:Saket Saurabh and Meirav Zehavi,
16127:from the original on 8 March 2014
16010:Limit inferior and limit superior
13955:
12007:both above (with constant factor
10777:{\displaystyle \sin x=\Omega (1)}
8425:{\displaystyle \varepsilon >0}
6242:{\displaystyle g(x)=h(x)+O(f(x))}
6096:)) as the class of all functions
5823:, but not if they are defined on
4892:Equivalently, the condition that
4011:{\displaystyle f\cdot O(g)=O(fg)}
2347:{\displaystyle |f(x)|\leq Mx^{4}}
1789:limit inferior and limit superior
1462:{\displaystyle |f(x)|\leq Mg(x).}
247:
42:
17590:(2008) . "1.6. Some notations".
16112:
15985:Asymptotically optimal algorithm
15706:{\displaystyle \prec \!\!\prec }
8898:definition of the big-O notation
6722:(·) on the left side, there are
6412:
5737:{\displaystyle f(n,m)=O(g(n,m))}
5310:
4997:
4956:
4822:
4792:
4762:
4674:
4657:
4632:
4608:{\displaystyle \mathbb {R} ^{n}}
3050:
3028:{\displaystyle T(n)\in O(n^{2})}
2299:is equivalent to its expansion,
1299:if there exist positive numbers
339:
17620:
17579:
17531:
17497:
17485:from the original on 2022-02-03
17446:
17419:
17306:
17184:
17168:
17130:
17076:
17065:from the original on 2016-03-10
16842:
16789:from the original on 2018-12-12
16716:
16703:Thomas H. Cormen et al., 2001,
16667:(2018), no. 12, 3844–3860.
16569:
16511:
16466:from the original on 2021-10-14
16442:Donald Knuth (June–July 1998).
16435:
16424:from the original on 2023-01-17
16370:from the original on 2023-01-17
16326:from the original on 2015-04-24
16174:. Boston/MA: PWS Publishing Co.
16024:: A precise method of bounding
15567:{\displaystyle f(x)\asymp g(x)}
15237:{\displaystyle f(x)\asymp g(x)}
14850:notation can be used to define
14032:
13735:, Hardy–Littlewood's big Omega
13479:{\displaystyle \Omega ,\omega }
11934:{\displaystyle f(n)\asymp g(n)}
9736:, which is defined as follows:
9704:The Hardy–Littlewood definition
9698:computational complexity theory
9520:Another asymptotic notation is
8983:{\displaystyle 2x^{2}=O(x^{2})}
8732:
8651:if for every positive constant
8623:
7196:{\displaystyle O((\log n)^{c})}
7148:as well as all operations in a
5855:{\displaystyle [0,\infty )^{2}}
5816:{\displaystyle [1,\infty )^{2}}
5518:
5374:
5100:
4667:
3532:
3038:and say that the algorithm has
2280:from above, the statement that
2224:. Mathematically, we can write
1573:
1274:
1038:
718:
17386:) is some function in the set
17147:Asymptotic Methods in Analysis
17136:for example it is omitted in:
16647:
16634:
16600:
16582:
16546:
16531:
16353:Asymptotic Methods in Analysis
16305:
16290:
16163:
15929:
15923:
15910:
15669:
15663:
15650:
15620:
15614:
15601:
15561:
15555:
15546:
15540:
15517:
15514:
15508:
15502:
15493:
15487:
15337:
15334:
15328:
15322:
15313:
15307:
15284:
15281:
15275:
15269:
15260:
15254:
15231:
15225:
15216:
15210:
14909:
14903:
14894:
14882:
14878:
14719:
14700:
14691:
14678:
14675:
14672:
14666:
14654:
14643:
14631:
14544:
14538:
14532:
14487:
14474:
14468:
14301:
14295:
14184:
14178:
14166:
14160:
14110:there exist positive constants
14093:
14087:
14045:
14039:
14033:
14029:
14026:
14020:
14014:
14005:
13999:
13982:consider the set of functions
13575:Computer science uses the big
13380:
13374:
13337:
13331:
13319:
13313:
13295:
13266:
13260:
13246:
13242:
13236:
13229:
13152:
13144:
13119:
13116:
13110:
13104:
13095:
13089:
13054:
13048:
13040:
13034:
13020:
12991:
12985:
12972:
12966:
12880:
12877:
12871:
12865:
12856:
12850:
12815:
12809:
12801:
12795:
12781:
12752:
12746:
12733:
12727:
12641:
12638:
12632:
12626:
12617:
12611:
12576:
12570:
12562:
12556:
12542:
12493:
12487:
12479:
12473:
12377:
12371:
12362:
12356:
12330:
12327:
12321:
12315:
12306:
12300:
12277:
12274:
12268:
12262:
12253:
12247:
12223:
12217:
12197:
12191:
12182:
12176:
11981:
11978:
11972:
11966:
11957:
11951:
11928:
11922:
11913:
11907:
11872:
11866:
11858:
11852:
11838:
11809:
11803:
11789:
11785:
11779:
11772:
11675:
11667:
11642:
11639:
11633:
11627:
11618:
11612:
11577:
11571:
11563:
11557:
11543:
11514:
11508:
11494:
11490:
11484:
11477:
11373:
11370:
11364:
11358:
11349:
11343:
11270:
11267:
11261:
11255:
11246:
11240:
11234:
11231:
11228:
11222:
11216:
11207:
11201:
11137:
11114:
11108:
11048:
11025:
11019:
10959:
10936:
10930:
10877:
10854:
10848:
10794:
10771:
10765:
10715:
10712:
10706:
10700:
10684:
10678:
10655:
10652:
10646:
10640:
10624:
10618:
10595:
10592:
10586:
10580:
10564:
10558:
10362:
10356:
10348:
10342:
10328:
10297:
10274:
10271:
10265:
10259:
10243:
10237:
10201:
10195:
10187:
10181:
10167:
10136:
10113:
10110:
10104:
10098:
10082:
10076:
9993:
9990:
9984:
9978:
9969:
9963:
9940:
9937:
9931:
9925:
9916:
9910:
9871:
9865:
9857:
9851:
9833:
9802:
9779:
9776:
9770:
9764:
9755:
9749:
9606:
9583:
9580:
9574:
9568:
9559:
9553:
9496:
9490:
9461:
9455:
9426:
9420:
9377:
9365:
9330:
9324:
9295:
9289:
9257:
9251:
9216:
9210:
9160:
9154:
9146:
9140:
9126:
9095:
9092:
9086:
9080:
9071:
9065:
9030:
9017:
8977:
8964:
8874:
8848:
8842:
8805:
8792:
8729:
8723:
8710:
8706:
8700:
8693:
8632:
8620:
8617:
8611:
8605:
8596:
8590:
8392:
8373:
8350:
8341:
8328:
8315:
8214:
8208:
8185:
8176:
8167:
8161:
8106:
8097:
8026:
8013:
7974:{\textstyle 0<\alpha <1}
7922:
7903:
7894:
7881:
7878:
7875:
7869:
7857:
7846:
7834:
7774:
7761:
7696:
7683:
7643:, loglinear, quasilinear, or "
7625:
7610:
7601:
7586:
7534:
7522:
7463:
7457:
7409:{\displaystyle O(n\log ^{*}n)}
7403:
7381:
7340:
7334:
7267:
7254:
7238:parallel random-access machine
7190:
7181:
7168:
7165:
7120:
7108:
7078:{\displaystyle O(\log \log n)}
7072:
7054:
7017:
7014:
7008:
7002:
6966:
6956:
6929:
6923:
6868:{\displaystyle {\mathcal {O}}}
6834:
6821:
6806:
6694:
6681:
6666:
6660:
6642:
6621:
6589:
6585:
6573:
6561:
6555:
6552:
6531:
6519:
6509:
6503:
6471:
6458:
6431:
6310:
6307:
6301:
6295:
6286:
6280:
6271:
6265:
6236:
6233:
6227:
6221:
6212:
6206:
6197:
6191:
6127:for some positive real number
5921:. Some consider this to be an
5873:
5843:
5830:
5804:
5791:
5731:
5728:
5716:
5710:
5701:
5689:
5660:
5648:
5619:
5607:
5527:
5515:
5502:
5493:
5481:
5389:
5371:
5358:
5349:
5337:
5233:
5219:
5208:
5204:
5178:
5172:
5160:
5153:
5115:
5097:
5085:
5050:
5038:
4800:
4796:
4788:
4781:
4770:
4766:
4758:
4751:
4678:
4664:
4661:
4653:
4647:
4636:
4628:
4524:{\displaystyle k\cdot f=O(g).}
4515:
4509:
4474:
4468:
4439:
4433:
4424:
4414:
4406:
4402:
4363:
4357:
4334:
4328:
4279:
4273:
4237:
4231:
4195:
4192:
4166:
4160:
4117:{\displaystyle f_{2}=O(g_{2})}
4111:
4098:
4068:{\displaystyle f_{1}=O(g_{1})}
4062:
4049:
4005:
3996:
3987:
3981:
3951:
3928:
3899:
3896:
3883:
3859:
3846:
3541:
3529:
3516:
3469:
3456:
3432:
3426:
3337:
3324:
3311:
3280:
3267:
3254:
3022:
3009:
3000:
2994:
2965:
2952:
2943:
2937:
2847:is 1000 times as large as the
2793:Big O notation is useful when
2658:
2618:
2508:
2490:
2462:
2422:
2324:
2320:
2314:
2307:
2025:{\displaystyle f(n)\leq Mg(n)}
2019:
2013:
2001:
1995:
1918:
1912:
1893:
1887:
1807:
1655:
1649:
1637:
1631:
1613:
1582:
1563:
1557:
1538:
1532:
1485:
1479:
1453:
1447:
1434:
1430:
1424:
1417:
1388:
1374:
1283:
1264:
1258:
1239:
1233:
1134:
1128:
1109:
1103:
1035:
1029:
1016:
1012:
1006:
999:
924:
918:
899:
893:
850:
844:
821:
815:
788:
782:
759:
753:
727:
708:
702:
683:
677:
634:
628:
279:
273:
257:
251:
105:
80:
77:
71:
65:
52:
46:
13:
1:
17145:. Department of Mathematics.
16225:)) is a set, we could write "
15991:Big O in probability notation
15789:{\displaystyle \preccurlyeq }
15746:{\displaystyle \preccurlyeq }
13364:The limit definitions assume
12383:{\displaystyle f(n)\sim g(n)}
12003:is asymptotically bounded by
11149:{\displaystyle x\to \infty .}
11060:{\displaystyle x\to \infty ;}
10971:{\displaystyle x\to \infty ,}
10889:{\displaystyle x\to \infty .}
10806:{\displaystyle x\to \infty ,}
9263:{\displaystyle c\cdot f=o(g)}
8886:{\displaystyle x\to \infty .}
7992:Factoring a number using the
7023:{\displaystyle O(\alpha (n))}
6718:functions which satisfy each
5025:. For example, the statement
3391:
2971:{\displaystyle T(n)=O(n^{2})}
17768:10.1007/978-3-540-25984-8_27
16566:(2013), no. 3, 477–501.
15343:{\displaystyle g(x)=O(f(x))}
15290:{\displaystyle f(x)=O(g(x))}
12336:{\displaystyle g(n)=O(f(n))}
12283:{\displaystyle f(n)=O(g(n))}
11648:{\displaystyle f(n)=O(g(n))}
11379:{\displaystyle f(n)=o(g(n))}
10306:{\displaystyle x\to \infty }
10145:{\displaystyle x\to \infty }
9999:{\displaystyle f(x)=o(g(x))}
9811:{\displaystyle x\to \infty }
9101:{\displaystyle f(x)=o(g(x))}
8461:Intuitively, the assertion "
8438:Related asymptotic notations
6742:(1), there is some function
6440:{\displaystyle n\to \infty }
6329:
5317:{\displaystyle \mathbf {x} }
4829:{\displaystyle \mathbf {x} }
4392:be a nonzero constant. Then
4384:Multiplication by a constant
3758:. This is not equivalent to
3642:We may ignore any powers of
506:, big O notation is used to
114:{\displaystyle x\to \infty }
7:
17734:. PWS Publishing. pp.
17235:" or sometimes just "oh of
16444:"Teach Calculus with Big O"
15967:
15848:Ivan Matveyevich Vinogradov
15130:{\displaystyle \Omega _{-}}
15103:{\displaystyle \Omega _{+}}
15076:{\displaystyle \Omega _{L}}
15049:{\displaystyle \Omega _{R}}
13775:notations. The small omega
13486:on functions correspond to
11657:Big O; Big Oh; Big Omicron
10492:{\displaystyle \Omega _{-}}
10465:{\displaystyle \Omega _{L}}
10438:{\displaystyle \Omega _{+}}
10411:{\displaystyle \Omega _{R}}
10387:These symbols were used by
10056:{\displaystyle \Omega _{L}}
10029:{\displaystyle \Omega _{R}}
8908:, the latter must hold for
8896:The difference between the
8811:{\displaystyle 2x=o(x^{2})}
8128:travelling salesman problem
8074:travelling salesman problem
7039:Disjoint-set data structure
6893:is a positive constant and
6417:In more complicated usage,
4918:{\displaystyle x_{i}\geq M}
4862:{\displaystyle x_{i}\geq M}
3691:are not of the same order.
3388:is close enough to 0.
3045:time complexity. The sign "
2363:and a positive real number
2058:{\displaystyle n\geq n_{0}}
320:{\displaystyle x\geq x_{0}}
34:Example of Big O notation:
10:
17955:
17705:Introduction to Algorithms
17658:Cambridge University Press
17573:Cambridge University Press
17429:Introduction to Algorithms
17317:Introduction to Algorithms
17227:)) (pronounced "big-oh of
17193:Introduction to Algorithms
17101:Introduction to Algorithms
16726:Introduction to algorithms
16193:Introduction to Algorithms
13963:Introduction to Algorithms
13802:
13545:{\displaystyle \geq ,>}
12895:Small Omega; Little Omega
9716:introduced the new symbol
9194:is a nonzero constant and
8453:
8191:{\displaystyle f(n)=O(n!)}
7433:of a simple polygon using
7033:inverse Ackermann function
6882:
6879:Orders of common functions
6726:functions satisfying each
6135:Other arithmetic operators
5456:) is quite different from
4285:{\displaystyle f_{2}=O(g)}
4243:{\displaystyle f_{1}=O(g)}
3818:
2918:(1,000,000) = 1,000,000 =
2068:
1339:such that for all defined
17463:SIAM Journal on Computing
16978:10.1007/978-3-642-38896-5
16068:Analytische Zahlentheorie
15025:(in the sense "is not an
14994:Analytische Zahlentheorie
13392:{\displaystyle g(n)>0}
8857:{\displaystyle 1/x=o(1),}
8198:is sometimes weakened to
7722:schoolbook multiplication
7126:{\displaystyle O(\log n)}
3726:. This can be written as
3061:Infinitesimal asymptotics
1828:extended real number line
587:valued function, and let
17406:+ 1, which is indeed in
17394:). In this case, we let
17243:") the set of functions
15850:introduced his notation
15463:{\displaystyle K\not =0}
15437:{\displaystyle f\sim Kg}
15000:"). The number theorist
9666:{\displaystyle -\infty }
8655:there exists a constant
8032:{\displaystyle O(c^{n})}
7780:{\displaystyle O(n^{c})}
7702:{\displaystyle O(n^{2})}
7305:{\textstyle 0<c<1}
7273:{\displaystyle O(n^{c})}
6985:; Using a constant-size
6978:{\displaystyle (-1)^{n}}
6840:{\displaystyle O(n^{2})}
5672:{\displaystyle g(n,m)=n}
5631:{\displaystyle f(n,m)=1}
2693:
483:Bachmann–Landau notation
17508:. Courier Corporation.
16891:10.1145/1008328.1008329
16606:{\displaystyle (k,n-k)}
16561:J. Scientific Computing
16170:Michael Sipser (1997).
15193:{\displaystyle \asymp }
15150:{\displaystyle \Omega }
15018:{\displaystyle \Omega }
13799:Use in computer science
13788:{\displaystyle \omega }
13748:{\displaystyle \Omega }
13728:{\displaystyle \asymp }
13668:{\displaystyle \Omega }
13648:{\displaystyle \omega }
13608:{\displaystyle \Theta }
13565:{\displaystyle \Omega }
13399:for sufficiently large
12392:Asymptotic equivalence
11693:(up to constant factor
11299:{\displaystyle \Omega }
11181:{\displaystyle \Omega }
9729:{\displaystyle \Omega }
9714:John Edensor Littlewood
9643:{\displaystyle \infty }
9533:{\displaystyle \Omega }
9505:{\displaystyle f=o(h).}
8542:grows much slower than
8520:grows much faster than
8144:all partitions of a set
5295:{\displaystyle n\geq M}
5269:{\displaystyle m\geq M}
3785:, then its run time is
3657:is exactly the same as
3601:are very different. If
1716:{\displaystyle \infty }
1312:{\displaystyle \delta }
356:Orders of approximation
226:{\displaystyle x_{0}=5}
17939:Analysis of algorithms
17670:Fundamental Algorithms
17140:"Asymptotic Notations"
16654:
16607:
16553:
16073:Analytic Number Theory
16036:Order of approximation
15939:
15884:
15864:
15840:
15810:
15809:{\displaystyle \prec }
15790:
15767:
15766:{\displaystyle \prec }
15747:
15727:
15707:
15679:
15627:
15568:
15524:
15464:
15438:
15409:
15374:
15344:
15291:
15238:
15194:
15174:
15151:
15131:
15104:
15077:
15050:
15019:
14998:analytic number theory
14916:
14781:
14743:
14551:
14494:
14311:
14218:
14058:
13805:Analysis of algorithms
13789:
13769:
13749:
13729:
13709:
13689:
13669:
13655:and Knuth's big Omega
13649:
13629:
13609:
13589:
13566:
13546:
13521:
13480:
13454:
13413:
13393:
13353:
13273:
13160:
13126:
13070:
12998:
12887:
12831:
12759:
12648:
12592:
12520:
12384:
12337:
12284:
12230:
12150:
12055:
12028:
11988:
11941:(Hardy's notation) or
11935:
11888:
11816:
11707:
11683:
11649:
11593:
11521:
11412:
11380:
11300:
11277:
11182:
11150:
11121:
11061:
11032:
10972:
10943:
10890:
10861:
10807:
10778:
10730:analytic number theory
10722:
10662:
10602:
10542:
10493:
10466:
10439:
10412:
10378:
10307:
10281:
10217:
10146:
10120:
10057:
10030:
10000:
9947:
9891:
9812:
9786:
9730:
9694:analytic number theory
9667:
9644:
9616:
9615:{\displaystyle x\to a}
9590:
9534:
9506:
9468:
9467:{\displaystyle g=o(h)}
9433:
9432:{\displaystyle f=o(g)}
9387:
9337:
9336:{\displaystyle g=o(G)}
9302:
9301:{\displaystyle f=o(F)}
9264:
9223:
9222:{\displaystyle f=o(g)}
9176:
9102:
9037:
8984:
8887:
8864: both as
8858:
8812:
8761:
8676:
8642:
8426:
8399:
8357:
8298:
8297:{\displaystyle c>0}
8271:
8270:{\displaystyle k>0}
8245:
8192:
8113:
8059:
8033:
7975:
7943:
7796:Tree-adjoining grammar
7781:
7703:
7656:fast Fourier transform
7632:
7567:
7410:
7347:
7306:
7274:
7223:
7197:
7127:
7079:
7024:
6979:
6936:
6869:
6841:
6708:
6441:
6320:
6252:expresses the same as
6243:
5856:
5817:
5778:
5758:
5738:
5673:
5632:
5588:
5537:
5450:
5399:
5318:
5296:
5270:
5241:
5125:
5015:
4980:
4939:
4919:
4886:
4863:
4830:
4808:
4737:
4736:{\displaystyle C>0}
4711:
4688:
4609:
4580:
4560:
4525:
4481:
4480:{\displaystyle f=O(g)}
4452:. In other words, if
4446:
4370:
4341:
4286:
4244:
4202:
4118:
4069:
4021:
4012:
3958:
3554:
3351:
3029:
2972:
2790:
2726:analysis of algorithms
2724:, it is useful in the
2685:
2604:
2348:
2059:
2026:
1979:
1952:
1932:
1867:
1847:
1820:
1781:
1761:
1741:
1717:
1697:
1674:
1592:
1512:
1492:
1463:
1402:
1353:
1333:
1313:
1293:
1217:
1191:
1177:near some real number
1171:
1151:
1087:
1067:
985:
958:
938:
877:
857:
828:
795:
766:
737:
661:
641:
601:
573:
512:analytic number theory
497:order of approximation
328:
321:
288:
227:
194:
167:
141:
140:{\displaystyle M>0}
115:
89:
17929:Mathematical notation
17692:Leiserson, Charles E.
17602:, with a foreword by
17506:Asymptotic Expansions
17088:Leiserson, Charles E.
17045:10.1145/382242.382835
16655:
16608:
16554:
16245:))" to indicate that
15940:
15885:
15865:
15841:
15811:
15791:
15768:
15748:
15728:
15708:
15680:
15628:
15569:
15525:
15465:
15439:
15410:
15375:
15345:
15292:
15239:
15195:
15175:
15173:{\displaystyle \sim }
15152:
15132:
15105:
15078:
15051:
15020:
14917:
14812:taking values in any
14782:
14780:{\displaystyle \ln n}
14744:
14561:. Some authors write
14552:
14495:
14312:
14219:
14059:
13803:Further information:
13790:
13770:
13768:{\displaystyle \sim }
13750:
13730:
13710:
13690:
13670:
13650:
13630:
13610:
13590:
13567:
13547:
13522:
13481:
13460:(Knuth's version of)
13455:
13414:
13394:
13354:
13274:
13161:
13127:
13071:
12999:
12888:
12832:
12760:
12649:
12593:
12521:
12385:
12338:
12285:
12231:
12151:
12056:
12054:{\displaystyle k_{1}}
12029:
12027:{\displaystyle k_{2}}
11989:
11936:
11889:
11817:
11708:
11684:
11650:
11594:
11522:
11413:
11381:
11301:
11278:
11183:
11151:
11122:
11062:
11033:
10973:
10944:
10891:
10862:
10808:
10779:
10723:
10663:
10603:
10543:
10494:
10467:
10440:
10413:
10379:
10308:
10282:
10218:
10147:
10121:
10058:
10031:
10001:
9948:
9892:
9813:
9787:
9731:
9668:
9645:
9630:is some real number,
9617:
9591:
9535:
9507:
9469:
9434:
9388:
9338:
9303:
9265:
9224:
9177:
9103:
9038:
8985:
8888:
8859:
8813:
8770:For example, one has
8762:
8677:
8675:{\displaystyle x_{0}}
8643:
8427:
8400:
8358:
8299:
8272:
8246:
8193:
8114:
8112:{\displaystyle O(n!)}
8060:
8034:
7976:
7944:
7782:
7704:
7633:
7568:
7411:
7348:
7307:
7275:
7224:
7198:
7144:or a balanced search
7128:
7080:
7025:
6980:
6937:
6883:Further information:
6870:
6842:
6709:
6442:
6321:
6244:
5857:
5818:
5779:
5759:
5739:
5674:
5633:
5589:
5538:
5451:
5400:
5319:
5297:
5271:
5242:
5126:
5016:
4981:
4940:
4920:
4887:
4864:
4831:
4809:
4738:
4712:
4689:
4610:
4581:
4561:
4526:
4482:
4447:
4371:
4342:
4287:
4245:
4208:. It follows that if
4203:
4119:
4070:
4013:
3959:
3631:integer factorization
3555:
3352:
3030:
2973:
2801:might be found to be
2780:
2742:appearing within the
2686:
2605:
2380:. To prove this, let
2349:
2073:In typical usage the
2060:
2027:
1980:
1978:{\displaystyle n_{0}}
1953:
1933:
1868:
1848:
1821:
1782:
1762:
1742:
1718:
1698:
1675:
1593:
1513:
1493:
1464:
1403:
1354:
1334:
1314:
1294:
1218:
1192:
1172:
1152:
1088:
1068:
986:
984:{\displaystyle x_{0}}
959:
939:
878:
858:
829:
796:
767:
738:
662:
642:
602:
574:
528:order of the function
516:arithmetical function
322:
289:
228:
195:
193:{\displaystyle x_{0}}
168:
142:
116:
90:
33:
17504:Erdelyi, A. (1956).
17494:See sect.2.3, p.551.
17175:Cormen et al. (2009)
16617:
16579:
16521:
16407:Concrete Mathematics
16297:Cormen et al. (2009)
16176:Here: Def.7.2, p.227
16047:References and notes
15979:Asymptotic expansion
15964:should not be used.
15897:
15874:
15863:{\displaystyle \ll }
15854:
15820:
15800:
15780:
15757:
15737:
15726:{\displaystyle \ll }
15717:
15692:
15637:
15588:
15534:
15481:
15448:
15419:
15384:
15354:
15301:
15248:
15204:
15184:
15164:
15141:
15114:
15087:
15060:
15033:
15009:
14927:equivalence relation
14865:
14765:
14618:
14504:
14443:
14242:
14081:
13993:
13779:
13759:
13739:
13719:
13699:
13679:
13659:
13639:
13619:
13599:
13579:
13556:
13530:
13490:
13464:
13423:
13403:
13368:
13284:
13176:
13166:is not dominated by
13140:
13083:
13009:
12911:
12844:
12770:
12672:
12662:is bounded below by
12605:
12531:
12410:
12350:
12294:
12241:
12159:
12067:
12038:
12011:
11945:
11901:
11827:
11719:
11697:
11663:
11606:
11532:
11424:
11402:
11337:
11290:
11195:
11172:
11160:The Knuth definition
11131:
11077:
11042:
10988:
10953:
10906:
10871:
10823:
10788:
10747:
10672:
10612:
10552:
10506:
10502:These three symbols
10476:
10449:
10422:
10395:
10317:
10291:
10231:
10156:
10130:
10070:
10040:
10013:
9957:
9904:
9822:
9796:
9743:
9720:
9710:Godfrey Harold Hardy
9654:
9634:
9600:
9547:
9524:
9478:
9443:
9408:
9396:It also satisfies a
9347:
9312:
9277:
9233:
9198:
9115:
9059:
8995:
8942:
8868:
8822:
8777:
8689:
8659:
8584:
8410:
8367:
8309:
8282:
8255:
8202:
8155:
8091:
8043:
8007:
7953:
7821:
7755:
7677:
7580:
7441:
7375:
7346:{\displaystyle O(n)}
7328:
7284:
7248:
7207:
7159:
7102:
7092:interpolation search
7048:
6996:
6953:
6935:{\displaystyle O(1)}
6917:
6855:
6815:
6451:
6425:
6259:
6185:
5981:from the identities
5827:
5788:
5768:
5748:
5683:
5642:
5601:
5550:
5463:
5412:
5331:
5306:
5280:
5254:
5149:
5032:
4990:
4949:
4929:
4896:
4873:
4840:
4818:
4747:
4721:
4701:
4622:
4590:
4570:
4550:
4491:
4456:
4396:
4369:{\displaystyle O(g)}
4351:
4296:
4254:
4212:
4128:
4079:
4030:
3969:
3827:
3575:, one may disregard
3420:
3085:
2988:
2931:
2795:analyzing algorithms
2773:Infinite asymptotics
2716:asymptotic expansion
2614:
2414:
2303:
2207:. Thus, we say that
2036:
1989:
1962:
1942:
1881:
1857:
1837:
1795:
1771:
1751:
1731:
1707:
1687:
1602:
1526:
1502:
1491:{\displaystyle g(x)}
1473:
1413:
1364:
1343:
1323:
1303:
1227:
1201:
1181:
1161:
1097:
1077:
995:
968:
948:
887:
867:
856:{\displaystyle g(x)}
838:
827:{\displaystyle f(x)}
809:
794:{\displaystyle g(x)}
776:
765:{\displaystyle f(x)}
747:
671:
651:
640:{\displaystyle g(x)}
622:
591:
563:
520:prime number theorem
412:Scientific modelling
402:Generalization error
298:
237:
204:
177:
151:
125:
99:
38:
17934:Asymptotic analysis
17798:"little-o notation"
16953:– via Numdam.
16030:integral transforms
14835:, i.e. to directed
14798:normed vector space
14590:) for any constant
14571:logarithmic factors
14569:notation, ignoring
14189: for all
13159:{\displaystyle |f|}
11682:{\displaystyle |f|}
10981:and more precisely
10816:and more precisely
9953:is the negation of
8735: for all
8078:dynamic programming
8058:{\textstyle c>1}
7658:; fastest possible
7222:{\textstyle c>1}
6774:. Thus for example
5869:Matters of notation
3781:of an input number
1216:{\displaystyle a=0}
1041: for all
508:classify algorithms
487:asymptotic notation
471:family of notations
381:Significant figures
166:{\displaystyle M=1}
121:since there exists
17907:2018-10-07 at the
16782:10.1007/BF02401834
16710:2009-01-16 at the
16650:
16603:
16549:
16482:2008-05-13 at the
16477:Unabridged version
15935:
15890:notation. We have
15880:
15860:
15836:
15806:
15786:
15763:
15743:
15723:
15703:
15675:
15633: and
15623:
15564:
15520:
15460:
15444:for some constant
15434:
15405:
15370:
15340:
15287:
15234:
15190:
15170:
15147:
15127:
15100:
15073:
15046:
15015:
14912:
14777:
14739:
14547:
14490:
14307:
14214:
14054:
13785:
13765:
13745:
13725:
13705:
13685:
13665:
13645:
13625:
13605:
13585:
13562:
13542:
13517:
13476:
13450:
13409:
13389:
13349:
13302:
13269:
13156:
13122:
13066:
13027:
12994:
12883:
12827:
12788:
12755:
12644:
12588:
12549:
12516:
12380:
12333:
12280:
12226:
12146:
12051:
12024:
11984:
11931:
11884:
11845:
11812:
11703:
11679:
11645:
11589:
11550:
11517:
11408:
11376:
11326:Formal definition
11296:
11273:
11178:
11146:
11117:
11057:
11028:
10968:
10939:
10886:
10857:
10803:
10774:
10718:
10658:
10598:
10538:
10489:
10462:
10435:
10408:
10374:
10335:
10303:
10277:
10213:
10174:
10142:
10116:
10053:
10026:
9996:
9943:
9887:
9840:
9808:
9782:
9726:
9663:
9640:
9612:
9586:
9530:
9516:Big Omega notation
9502:
9464:
9429:
9383:
9333:
9298:
9260:
9219:
9172:
9133:
9098:
9033:
8980:
8920:stronger statement
8912:positive constant
8883:
8854:
8808:
8757:
8672:
8638:
8531:, or equivalently
8422:
8395:
8353:
8294:
8267:
8241:
8188:
8109:
8082:brute-force search
8055:
8029:
7998:number field sieve
7971:
7939:
7777:
7720:-digit numbers by
7699:
7628:
7563:
7558:
7435:Seidel's algorithm
7406:
7343:
7302:
7270:
7219:
7193:
7123:
7087:double logarithmic
7075:
7020:
6975:
6932:
6865:
6837:
6772:symmetric relation
6704:
6702:
6437:
6316:
6239:
6084:))"), thinking of
5852:
5813:
5774:
5754:
5734:
5669:
5628:
5584:
5533:
5446:
5395:
5314:
5292:
5266:
5237:
5121:
5011:
4976:
4935:
4915:
4885:{\displaystyle i.}
4882:
4859:
4826:
4804:
4733:
4707:
4684:
4605:
4576:
4556:
4534:Multiple variables
4521:
4477:
4442:
4366:
4337:
4282:
4240:
4198:
4114:
4065:
4008:
3954:
3550:
3347:
3345:
3072:exponential series
3025:
2968:
2906:grows larger than
2791:
2785:versus input size
2681:
2600:
2598:
2344:
2055:
2022:
1975:
1948:
1928:
1863:
1843:
1816:
1815:
1814:
1777:
1757:
1737:
1727:of the domains of
1713:
1693:
1670:
1620:
1588:
1508:
1488:
1459:
1398:
1349:
1329:
1309:
1289:
1213:
1187:
1167:
1147:
1083:
1063:
981:
964:and a real number
954:
934:
873:
853:
824:
791:
762:
733:
657:
637:
597:
569:
389:Other fundamentals
329:
317:
284:
282:
260:
223:
190:
163:
137:
111:
85:
83:
55:
17745:978-0-534-94728-6
17715:978-0-262-03293-3
17696:Rivest, Ronald L.
17688:Cormen, Thomas H.
17679:978-0-201-89683-1
17613:978-0-19-921985-8
17596:D. R. Heath-Brown
17515:978-0-486-60318-6
17476:10.1137/070683933
17332:978-0-262-53305-8
17202:978-0-262-53305-8
17138:Hildebrand, A.J.
17092:Rivest, Ronald L.
17084:Cormen, Thomas H.
17011:Meertens, Lambert
16987:978-3-642-38896-5
16736:978-0-262-27083-0
16417:978-0-201-55802-9
16363:978-0-486-64221-5
16253:) is a member of
16208:978-0-262-53305-8
16022:Nachbin's theorem
15883:{\displaystyle O}
14856:differentiability
14814:topological group
14557:for any constant
14535:
14471:
14435:is polynomial in
14190:
14150:
14146:
14142:
14129:
14125:
14121:
14115:
14111:
14050:
13708:{\displaystyle o}
13688:{\displaystyle O}
13628:{\displaystyle o}
13588:{\displaystyle O}
13412:{\displaystyle n}
13362:
13361:
13341:
13287:
13058:
13012:
12819:
12773:
12580:
12534:
12497:
11994:(Knuth notation)
11876:
11830:
11706:{\displaystyle k}
11581:
11535:
11411:{\displaystyle k}
11329:Limit definition
10366:
10320:
10205:
10159:
9875:
9825:
9164:
9118:
9108:is equivalent to
8926:is also big-O of
8736:
8627:
8553:. As before, let
8450:Little-o notation
8149:
8148:
8140:Laplace expansion
7798:parsing; maximum
7545:
7488:
7364:-bit integers by
6393:. Here the terms
5923:abuse of notation
5777:{\displaystyle g}
5757:{\displaystyle f}
5522:
5477:
5378:
5104:
4938:{\displaystyle i}
4710:{\displaystyle M}
4671:
4642:
4579:{\displaystyle g}
4559:{\displaystyle f}
3865:
3633:and the function
3536:
3332:
3275:
3246:
3204:
3191:
3166:
3141:
3055:abuse of notation
2824:grows large, the
2789:for each function
2278:formal definition
2120:For example, let
2116:) can be omitted.
1951:{\displaystyle M}
1875:positive integers
1866:{\displaystyle g}
1846:{\displaystyle f}
1830:) always exists.
1826:(at least on the
1799:
1780:{\displaystyle a}
1760:{\displaystyle g}
1740:{\displaystyle f}
1696:{\displaystyle a}
1659:
1605:
1577:
1511:{\displaystyle x}
1352:{\displaystyle x}
1332:{\displaystyle M}
1278:
1190:{\displaystyle a}
1170:{\displaystyle f}
1086:{\displaystyle x}
1042:
957:{\displaystyle M}
876:{\displaystyle x}
722:
660:{\displaystyle x}
600:{\displaystyle g}
572:{\displaystyle f}
555:Formal definition
459:limiting behavior
448:
447:
407:Taylor polynomial
334:Fit approximation
16:(Redirected from
17946:
17876:
17874:
17872:
17855:
17853:
17851:
17834:
17832:
17830:
17813:
17811:
17809:
17792:
17790:
17788:
17777:"big-O notation"
17771:
17761:
17749:
17733:
17719:
17683:
17661:
17635:
17624:
17618:
17617:
17583:
17577:
17576:
17559:
17553:
17552:
17535:
17529:
17526:
17520:
17519:
17501:
17495:
17493:
17491:
17490:
17484:
17459:
17450:
17444:
17443:
17423:
17417:
17416:
17320:
17310:
17304:
17303:
17215:), we denote by
17188:
17182:
17172:
17166:
17165:
17163:
17161:
17155:
17144:
17134:
17128:
17125:
17116:
17115:
17080:
17074:
17073:
17071:
17070:
17064:
17057:
17047:
17037:
17019:
17003:
16992:
16991:
16961:
16955:
16954:
16952:
16950:
16944:
16921:
16912:
16906:
16905:
16903:
16893:
16869:
16852:
16849:Gérald Tenenbaum
16846:
16840:
16834:
16825:
16822:
16816:
16815:, vol. 41, 1916.
16812:Acta Mathematica
16807:
16798:
16797:
16795:
16794:
16784:
16769:Acta Mathematica
16760:
16749:
16748:
16720:
16714:
16701:
16695:
16694:
16677:
16668:
16659:
16657:
16656:
16651:
16646:
16645:
16633:
16632:
16627:
16626:
16612:
16610:
16609:
16604:
16573:
16567:
16558:
16556:
16555:
16550:
16530:
16529:
16515:
16509:
16502:
16496:
16493:
16487:
16474:
16472:
16471:
16465:
16448:
16439:
16433:
16432:
16430:
16429:
16390:
16379:
16378:
16376:
16375:
16344:
16335:
16334:
16332:
16331:
16325:
16318:
16312:Howell, Rodney.
16309:
16303:
16294:
16288:
16287:
16196:
16186:
16177:
16175:
16167:
16161:
16160:
16143:
16137:
16136:
16134:
16132:
16126:
16119:
16110:
16104:
16103:
16086:
16077:
16076:
16059:
16026:complex analytic
15944:
15942:
15941:
15936:
15889:
15887:
15886:
15881:
15869:
15867:
15866:
15861:
15845:
15843:
15842:
15837:
15815:
15813:
15812:
15807:
15795:
15793:
15792:
15787:
15776:Hardy's symbols
15772:
15770:
15769:
15764:
15752:
15750:
15749:
15744:
15732:
15730:
15729:
15724:
15712:
15710:
15709:
15704:
15684:
15682:
15681:
15676:
15632:
15630:
15629:
15624:
15573:
15571:
15570:
15565:
15529:
15527:
15526:
15521:
15469:
15467:
15466:
15461:
15443:
15441:
15440:
15435:
15414:
15412:
15411:
15406:
15379:
15377:
15376:
15371:
15349:
15347:
15346:
15341:
15296:
15294:
15293:
15288:
15244:means that both
15243:
15241:
15240:
15235:
15199:
15197:
15196:
15191:
15179:
15177:
15176:
15171:
15156:
15154:
15153:
15148:
15136:
15134:
15133:
15128:
15126:
15125:
15109:
15107:
15106:
15101:
15099:
15098:
15082:
15080:
15079:
15074:
15072:
15071:
15055:
15053:
15052:
15047:
15045:
15044:
15024:
15022:
15021:
15016:
14971:
14921:
14919:
14918:
14913:
14830:
14788:
14786:
14784:
14783:
14778:
14748:
14746:
14745:
14740:
14735:
14734:
14733:
14732:
14699:
14698:
14630:
14629:
14600:
14556:
14554:
14553:
14548:
14537:
14536:
14528:
14516:
14515:
14499:
14497:
14496:
14491:
14486:
14485:
14473:
14472:
14464:
14458:
14457:
14434:
14423:
14388:
14316:
14314:
14313:
14308:
14288:
14287:
14257:
14256:
14223:
14221:
14220:
14215:
14207:
14206:
14191:
14188:
14148:
14147:
14144:
14140:
14139:
14138:
14127:
14126:
14123:
14119:
14113:
14112:
14109:
14063:
14061:
14060:
14055:
14048:
13890:
13874:
13854:
13794:
13792:
13791:
13786:
13774:
13772:
13771:
13766:
13754:
13752:
13751:
13746:
13734:
13732:
13731:
13726:
13714:
13712:
13711:
13706:
13694:
13692:
13691:
13686:
13674:
13672:
13671:
13666:
13654:
13652:
13651:
13646:
13634:
13632:
13631:
13626:
13614:
13612:
13611:
13606:
13594:
13592:
13591:
13586:
13571:
13569:
13568:
13563:
13551:
13549:
13548:
13543:
13526:
13524:
13523:
13518:
13485:
13483:
13482:
13477:
13459:
13457:
13456:
13451:
13418:
13416:
13415:
13410:
13398:
13396:
13395:
13390:
13358:
13356:
13355:
13350:
13342:
13340:
13326:
13322:
13304:
13301:
13278:
13276:
13275:
13270:
13249:
13232:
13224:
13223:
13204:
13203:
13169:
13165:
13163:
13162:
13157:
13155:
13147:
13131:
13129:
13128:
13123:
13075:
13073:
13072:
13067:
13059:
13057:
13043:
13029:
13026:
13003:
13001:
13000:
12995:
12959:
12958:
12939:
12938:
12904:
12900:
12892:
12890:
12889:
12884:
12836:
12834:
12833:
12828:
12820:
12818:
12804:
12790:
12787:
12764:
12762:
12761:
12756:
12720:
12719:
12700:
12699:
12665:
12661:
12653:
12651:
12650:
12645:
12597:
12595:
12594:
12589:
12581:
12579:
12565:
12551:
12548:
12525:
12523:
12522:
12517:
12509:
12505:
12498:
12496:
12482:
12468:
12458:
12457:
12438:
12437:
12401:
12397:
12389:
12387:
12386:
12381:
12342:
12340:
12339:
12334:
12289:
12287:
12286:
12281:
12235:
12233:
12232:
12227:
12212:
12211:
12171:
12170:
12155:
12153:
12152:
12147:
12142:
12141:
12122:
12121:
12102:
12101:
12082:
12081:
12060:
12058:
12057:
12052:
12050:
12049:
12033:
12031:
12030:
12025:
12023:
12022:
12006:
12002:
11993:
11991:
11990:
11985:
11940:
11938:
11937:
11932:
11893:
11891:
11890:
11885:
11877:
11875:
11861:
11847:
11844:
11821:
11819:
11818:
11813:
11792:
11775:
11767:
11766:
11747:
11746:
11712:
11710:
11709:
11704:
11692:
11688:
11686:
11685:
11680:
11678:
11670:
11654:
11652:
11651:
11646:
11598:
11596:
11595:
11590:
11582:
11580:
11566:
11552:
11549:
11526:
11524:
11523:
11518:
11497:
11480:
11472:
11471:
11452:
11451:
11417:
11415:
11414:
11409:
11397:
11394:is dominated by
11393:
11385:
11383:
11382:
11377:
11314:
11313:
11305:
11303:
11302:
11297:
11282:
11280:
11279:
11274:
11187:
11185:
11184:
11179:
11155:
11153:
11152:
11147:
11126:
11124:
11123:
11118:
11107:
11106:
11066:
11064:
11063:
11058:
11037:
11035:
11034:
11029:
11018:
11017:
10977:
10975:
10974:
10969:
10948:
10946:
10945:
10940:
10895:
10893:
10892:
10887:
10866:
10864:
10863:
10858:
10847:
10846:
10812:
10810:
10809:
10804:
10783:
10781:
10780:
10775:
10727:
10725:
10724:
10719:
10699:
10698:
10667:
10665:
10664:
10659:
10639:
10638:
10607:
10605:
10604:
10599:
10579:
10578:
10547:
10545:
10544:
10539:
10537:
10536:
10524:
10523:
10498:
10496:
10495:
10490:
10488:
10487:
10471:
10469:
10468:
10463:
10461:
10460:
10444:
10442:
10441:
10436:
10434:
10433:
10417:
10415:
10414:
10409:
10407:
10406:
10383:
10381:
10380:
10375:
10367:
10365:
10351:
10337:
10334:
10312:
10310:
10309:
10304:
10286:
10284:
10283:
10278:
10258:
10257:
10222:
10220:
10219:
10214:
10206:
10204:
10190:
10176:
10173:
10151:
10149:
10148:
10143:
10125:
10123:
10122:
10117:
10097:
10096:
10062:
10060:
10059:
10054:
10052:
10051:
10035:
10033:
10032:
10027:
10025:
10024:
10005:
10003:
10002:
9997:
9952:
9950:
9949:
9944:
9896:
9894:
9893:
9888:
9880:
9876:
9874:
9860:
9846:
9839:
9817:
9815:
9814:
9809:
9791:
9789:
9788:
9783:
9735:
9733:
9732:
9727:
9672:
9670:
9669:
9664:
9649:
9647:
9646:
9641:
9621:
9619:
9618:
9613:
9595:
9593:
9592:
9587:
9539:
9537:
9536:
9531:
9511:
9509:
9508:
9503:
9473:
9471:
9470:
9465:
9438:
9436:
9435:
9430:
9392:
9390:
9389:
9384:
9342:
9340:
9339:
9334:
9307:
9305:
9304:
9299:
9269:
9267:
9266:
9261:
9228:
9226:
9225:
9220:
9193:
9181:
9179:
9178:
9173:
9165:
9163:
9149:
9135:
9132:
9107:
9105:
9104:
9099:
9044:
9042:
9040:
9039:
9034:
9029:
9028:
9010:
9009:
8989:
8987:
8986:
8981:
8976:
8975:
8957:
8956:
8917:
8892:
8890:
8889:
8884:
8863:
8861:
8860:
8855:
8832:
8817:
8815:
8814:
8809:
8804:
8803:
8766:
8764:
8763:
8758:
8753:
8752:
8737:
8734:
8713:
8696:
8681:
8679:
8678:
8673:
8671:
8670:
8654:
8647:
8645:
8644:
8639:
8628:
8625:
8552:
8541:
8530:
8519:
8508:
8497:
8486:
8471:
8433:
8431:
8429:
8428:
8423:
8404:
8402:
8401:
8396:
8391:
8390:
8362:
8360:
8359:
8354:
8349:
8348:
8327:
8326:
8305:
8303:
8301:
8300:
8295:
8276:
8274:
8273:
8268:
8250:
8248:
8247:
8242:
8240:
8236:
8235:
8197:
8195:
8194:
8189:
8118:
8116:
8115:
8110:
8064:
8062:
8061:
8056:
8038:
8036:
8035:
8030:
8025:
8024:
7980:
7978:
7977:
7972:
7948:
7946:
7945:
7940:
7938:
7937:
7936:
7935:
7902:
7901:
7833:
7832:
7812:LU decomposition
7804:bipartite graphs
7786:
7784:
7783:
7778:
7773:
7772:
7716:Multiplying two
7708:
7706:
7705:
7700:
7695:
7694:
7637:
7635:
7634:
7629:
7572:
7570:
7569:
7564:
7562:
7561:
7546:
7543:
7518:
7517:
7489:
7486:
7453:
7452:
7415:
7413:
7412:
7407:
7396:
7395:
7352:
7350:
7349:
7344:
7314:fractional power
7311:
7309:
7308:
7303:
7279:
7277:
7276:
7271:
7266:
7265:
7228:
7226:
7225:
7220:
7202:
7200:
7199:
7194:
7189:
7188:
7132:
7130:
7129:
7124:
7084:
7082:
7081:
7076:
7029:
7027:
7026:
7021:
6984:
6982:
6981:
6976:
6974:
6973:
6941:
6939:
6938:
6933:
6900:
6899:
6874:
6872:
6871:
6866:
6864:
6863:
6846:
6844:
6843:
6838:
6833:
6832:
6802:
6788:
6713:
6711:
6710:
6705:
6703:
6693:
6692:
6670:
6669:
6641:
6640:
6636:
6614:
6613:
6597:
6596:
6551:
6550:
6546:
6496:
6495:
6479:
6478:
6446:
6444:
6443:
6438:
6400:
6392:
6369:
6325:
6323:
6322:
6317:
6248:
6246:
6245:
6240:
6161:
6126:
6116:
6072:) is in the set
6051:is an element of
6040:
6010:
5995:
5980:
5966:
5947:
5920:
5861:
5859:
5858:
5853:
5851:
5850:
5822:
5820:
5819:
5814:
5812:
5811:
5783:
5781:
5780:
5775:
5763:
5761:
5760:
5755:
5743:
5741:
5740:
5735:
5678:
5676:
5675:
5670:
5637:
5635:
5634:
5629:
5593:
5591:
5590:
5585:
5542:
5540:
5539:
5534:
5523:
5520:
5514:
5513:
5475:
5455:
5453:
5452:
5447:
5404:
5402:
5401:
5396:
5379:
5376:
5370:
5369:
5323:
5321:
5320:
5315:
5313:
5301:
5299:
5298:
5293:
5275:
5273:
5272:
5267:
5250:whenever either
5246:
5244:
5243:
5238:
5236:
5222:
5211:
5203:
5202:
5190:
5189:
5156:
5130:
5128:
5127:
5122:
5105:
5102:
5078:
5077:
5065:
5064:
5020:
5018:
5017:
5012:
5010:
5009:
5000:
4985:
4983:
4982:
4977:
4969:
4968:
4959:
4944:
4942:
4941:
4936:
4924:
4922:
4921:
4916:
4908:
4907:
4891:
4889:
4888:
4883:
4868:
4866:
4865:
4860:
4852:
4851:
4835:
4833:
4832:
4827:
4825:
4813:
4811:
4810:
4805:
4803:
4795:
4784:
4773:
4765:
4754:
4742:
4740:
4739:
4734:
4716:
4714:
4713:
4708:
4693:
4691:
4690:
4685:
4677:
4672:
4669:
4660:
4643:
4640:
4635:
4614:
4612:
4611:
4606:
4604:
4603:
4598:
4585:
4583:
4582:
4577:
4565:
4563:
4562:
4557:
4530:
4528:
4527:
4522:
4486:
4484:
4483:
4478:
4451:
4449:
4448:
4443:
4417:
4409:
4391:
4375:
4373:
4372:
4367:
4346:
4344:
4343:
4338:
4321:
4320:
4308:
4307:
4291:
4289:
4288:
4283:
4266:
4265:
4249:
4247:
4246:
4241:
4224:
4223:
4207:
4205:
4204:
4199:
4191:
4190:
4178:
4177:
4153:
4152:
4140:
4139:
4123:
4121:
4120:
4115:
4110:
4109:
4091:
4090:
4074:
4072:
4071:
4066:
4061:
4060:
4042:
4041:
4017:
4015:
4014:
4009:
3963:
3961:
3960:
3955:
3950:
3949:
3940:
3939:
3921:
3920:
3911:
3910:
3895:
3894:
3876:
3875:
3866:
3863:
3858:
3857:
3839:
3838:
3814:
3800:itself, because
3799:
3795:
3784:
3776:
3772:
3761:
3757:
3753:
3747:
3743:
3739:
3725:
3719:
3710:
3704:
3700:
3690:
3686:
3682:
3667:
3656:
3645:
3638:
3624:
3614:
3610:
3604:
3600:
3589:
3570:
3566:
3559:
3557:
3556:
3551:
3537:
3534:
3528:
3527:
3509:
3508:
3493:
3492:
3477:
3476:
3412:
3401:
3396:If the function
3356:
3354:
3353:
3348:
3346:
3333:
3330:
3323:
3322:
3289:
3276:
3273:
3266:
3265:
3247:
3242:
3241:
3232:
3212:
3205:
3202:
3192:
3190:
3182:
3181:
3172:
3167:
3165:
3157:
3156:
3147:
3142:
3140:
3132:
3131:
3122:
3101:
3100:
3077:
3048:
3043:
3034:
3032:
3031:
3026:
3021:
3020:
2977:
2975:
2974:
2969:
2964:
2963:
2923:
2909:
2905:
2901:
2887:
2873:
2867:
2853:
2846:
2839:
2829:
2823:
2819:
2800:
2788:
2784:
2748:
2741:
2722:computer science
2690:
2688:
2687:
2682:
2677:
2676:
2661:
2650:
2649:
2634:
2633:
2621:
2609:
2607:
2606:
2601:
2599:
2595:
2594:
2576:
2572:
2571:
2556:
2555:
2540:
2539:
2521:
2511:
2506:
2505:
2493:
2485:
2484:
2465:
2454:
2453:
2438:
2437:
2425:
2409:
2397:. Then, for all
2396:
2389:
2379:
2366:
2362:
2353:
2351:
2350:
2345:
2343:
2342:
2327:
2310:
2298:
2275:
2261:
2242:
2223:
2218:is a "big O" of
2217:
2206:
2200:
2194:
2188:
2185:is a product of
2184:
2177:
2170:
2166:
2162:
2155:
2148:
2144:
2138:
2115:
2111:
2097:
2082:
2078:
2064:
2062:
2061:
2056:
2054:
2053:
2031:
2029:
2028:
2023:
1984:
1982:
1981:
1976:
1974:
1973:
1957:
1955:
1954:
1949:
1937:
1935:
1934:
1929:
1927:
1926:
1908:
1907:
1872:
1870:
1869:
1864:
1852:
1850:
1849:
1844:
1825:
1823:
1822:
1817:
1813:
1786:
1784:
1783:
1778:
1766:
1764:
1763:
1758:
1746:
1744:
1743:
1738:
1722:
1720:
1719:
1714:
1702:
1700:
1699:
1694:
1679:
1677:
1676:
1671:
1660:
1658:
1644:
1640:
1622:
1619:
1597:
1595:
1594:
1589:
1578:
1575:
1572:
1571:
1553:
1552:
1517:
1515:
1514:
1509:
1497:
1495:
1494:
1489:
1468:
1466:
1465:
1460:
1437:
1420:
1409:
1407:
1405:
1404:
1399:
1391:
1377:
1358:
1356:
1355:
1350:
1338:
1336:
1335:
1330:
1318:
1316:
1315:
1310:
1298:
1296:
1295:
1290:
1279:
1276:
1273:
1272:
1254:
1253:
1222:
1220:
1219:
1214:
1196:
1194:
1193:
1188:
1176:
1174:
1173:
1168:
1156:
1154:
1153:
1148:
1143:
1142:
1124:
1123:
1092:
1090:
1089:
1084:
1072:
1070:
1069:
1064:
1059:
1058:
1043:
1040:
1019:
1002:
990:
988:
987:
982:
980:
979:
963:
961:
960:
955:
943:
941:
940:
935:
933:
932:
914:
913:
882:
880:
879:
874:
862:
860:
859:
854:
833:
831:
830:
825:
800:
798:
797:
792:
771:
769:
768:
763:
743:and it is read "
742:
740:
739:
734:
723:
720:
717:
716:
698:
697:
666:
664:
663:
658:
646:
644:
643:
638:
614:of the positive
606:
604:
603:
598:
578:
576:
575:
570:
550:
546:
504:computer science
440:
433:
426:
343:
331:
330:
326:
324:
323:
318:
316:
315:
293:
291:
290:
285:
283:
261:
232:
230:
229:
224:
216:
215:
199:
197:
196:
191:
189:
188:
172:
170:
169:
164:
146:
144:
143:
138:
120:
118:
117:
112:
94:
92:
91:
86:
84:
56:
21:
17954:
17953:
17949:
17948:
17947:
17945:
17944:
17943:
17919:
17918:
17909:Wayback Machine
17883:
17870:
17868:
17849:
17847:
17828:
17826:
17807:
17805:
17786:
17784:
17759:
17746:
17724:Sipser, Michael
17716:
17700:Stein, Clifford
17680:
17643:
17641:Further reading
17638:
17625:
17621:
17614:
17600:J. H. Silverman
17584:
17580:
17560:
17556:
17536:
17532:
17527:
17523:
17516:
17502:
17498:
17488:
17486:
17482:
17457:
17451:
17447:
17440:
17424:
17420:
17333:
17311:
17307:
17300:
17273:
17203:
17189:
17185:
17173:
17169:
17159:
17157:
17153:
17142:
17135:
17131:
17126:
17119:
17112:
17096:Stein, Clifford
17081:
17077:
17068:
17066:
17062:
17035:10.1.1.694.3072
17022:ACM SIGACT News
17017:
17004:
16995:
16988:
16962:
16958:
16948:
16946:
16942:
16919:
16913:
16909:
16870:
16855:
16847:
16843:
16837:Aleksandar Ivić
16835:
16828:
16823:
16819:
16808:
16801:
16792:
16790:
16761:
16752:
16737:
16721:
16717:
16712:Wayback Machine
16702:
16698:
16678:
16671:
16641:
16637:
16628:
16622:
16621:
16620:
16618:
16615:
16614:
16580:
16577:
16576:
16574:
16570:
16525:
16524:
16522:
16519:
16518:
16516:
16512:
16503:
16499:
16494:
16490:
16484:Wayback Machine
16469:
16467:
16463:
16446:
16440:
16436:
16427:
16425:
16418:
16402:Patashnik, Oren
16391:
16382:
16373:
16371:
16364:
16348:N. G. de Bruijn
16345:
16338:
16329:
16327:
16323:
16316:
16310:
16306:
16295:
16291:
16209:
16187:
16180:
16168:
16164:
16144:
16140:
16130:
16128:
16124:
16117:
16111:
16107:
16087:
16080:
16060:
16053:
16049:
16005:
15998:
15970:
15898:
15895:
15894:
15875:
15872:
15871:
15855:
15852:
15851:
15821:
15818:
15817:
15801:
15798:
15797:
15781:
15778:
15777:
15758:
15755:
15754:
15738:
15735:
15734:
15718:
15715:
15714:
15693:
15690:
15689:
15638:
15635:
15634:
15589:
15586:
15585:
15535:
15532:
15531:
15482:
15479:
15478:
15449:
15446:
15445:
15420:
15417:
15416:
15385:
15382:
15381:
15355:
15352:
15351:
15302:
15299:
15298:
15249:
15246:
15245:
15205:
15202:
15201:
15185:
15182:
15181:
15165:
15162:
15161:
15142:
15139:
15138:
15121:
15117:
15115:
15112:
15111:
15094:
15090:
15088:
15085:
15084:
15067:
15063:
15061:
15058:
15057:
15040:
15036:
15034:
15031:
15030:
15010:
15007:
15006:
14986:
14962:
14866:
14863:
14862:
14829:
14817:
14794:
14766:
14763:
14762:
14761:
14722:
14718:
14694:
14690:
14653:
14649:
14625:
14621:
14619:
14616:
14615:
14595:
14527:
14526:
14511:
14507:
14505:
14502:
14501:
14481:
14477:
14463:
14462:
14453:
14449:
14444:
14441:
14440:
14425:
14394:
14360:
14323:
14283:
14279:
14252:
14248:
14243:
14240:
14239:
14202:
14198:
14187:
14143:
14134:
14130:
14122:
14108:
14082:
14079:
14078:
13994:
13991:
13990:
13958:
13877:
13857:
13837:
13807:
13801:
13780:
13777:
13776:
13760:
13757:
13756:
13740:
13737:
13736:
13720:
13717:
13716:
13700:
13697:
13696:
13680:
13677:
13676:
13660:
13657:
13656:
13640:
13637:
13636:
13635:, little omega
13620:
13617:
13616:
13600:
13597:
13596:
13580:
13577:
13576:
13557:
13554:
13553:
13531:
13528:
13527:
13491:
13488:
13487:
13465:
13462:
13461:
13424:
13421:
13420:
13404:
13401:
13400:
13369:
13366:
13365:
13327:
13309:
13305:
13303:
13291:
13285:
13282:
13281:
13245:
13228:
13219:
13215:
13199:
13195:
13177:
13174:
13173:
13170:asymptotically
13167:
13151:
13143:
13141:
13138:
13137:
13084:
13081:
13080:
13044:
13030:
13028:
13016:
13010:
13007:
13006:
12954:
12950:
12934:
12930:
12912:
12909:
12908:
12905:asymptotically
12902:
12898:
12845:
12842:
12841:
12805:
12791:
12789:
12777:
12771:
12768:
12767:
12715:
12711:
12695:
12691:
12673:
12670:
12669:
12666:asymptotically
12663:
12659:
12606:
12603:
12602:
12566:
12552:
12550:
12538:
12532:
12529:
12528:
12483:
12469:
12467:
12466:
12462:
12453:
12449:
12433:
12429:
12411:
12408:
12407:
12399:
12395:
12351:
12348:
12347:
12295:
12292:
12291:
12242:
12239:
12238:
12207:
12203:
12166:
12162:
12160:
12157:
12156:
12137:
12133:
12117:
12113:
12097:
12093:
12077:
12073:
12068:
12065:
12064:
12045:
12041:
12039:
12036:
12035:
12018:
12014:
12012:
12009:
12008:
12004:
12000:
11946:
11943:
11942:
11902:
11899:
11898:
11862:
11848:
11846:
11834:
11828:
11825:
11824:
11788:
11771:
11762:
11758:
11742:
11738:
11720:
11717:
11716:
11698:
11695:
11694:
11690:
11674:
11666:
11664:
11661:
11660:
11607:
11604:
11603:
11567:
11553:
11551:
11539:
11533:
11530:
11529:
11493:
11476:
11467:
11463:
11447:
11443:
11425:
11422:
11421:
11403:
11400:
11399:
11395:
11391:
11338:
11335:
11334:
11312:
11291:
11288:
11287:
11196:
11193:
11192:
11173:
11170:
11169:
11162:
11132:
11129:
11128:
11102:
11098:
11078:
11075:
11074:
11043:
11040:
11039:
11013:
11009:
10989:
10986:
10985:
10954:
10951:
10950:
10907:
10904:
10903:
10872:
10869:
10868:
10842:
10838:
10824:
10821:
10820:
10789:
10786:
10785:
10748:
10745:
10744:
10738:
10736:Simple examples
10694:
10690:
10673:
10670:
10669:
10634:
10630:
10613:
10610:
10609:
10574:
10570:
10553:
10550:
10549:
10532:
10528:
10519:
10515:
10507:
10504:
10503:
10483:
10479:
10477:
10474:
10473:
10456:
10452:
10450:
10447:
10446:
10429:
10425:
10423:
10420:
10419:
10402:
10398:
10396:
10393:
10392:
10352:
10338:
10336:
10324:
10318:
10315:
10314:
10292:
10289:
10288:
10253:
10249:
10232:
10229:
10228:
10191:
10177:
10175:
10163:
10157:
10154:
10153:
10131:
10128:
10127:
10092:
10088:
10071:
10068:
10067:
10047:
10043:
10041:
10038:
10037:
10020:
10016:
10014:
10011:
10010:
9958:
9955:
9954:
9905:
9902:
9901:
9861:
9847:
9845:
9841:
9829:
9823:
9820:
9819:
9797:
9794:
9793:
9744:
9741:
9740:
9721:
9718:
9717:
9706:
9655:
9652:
9651:
9635:
9632:
9631:
9601:
9598:
9597:
9548:
9545:
9544:
9525:
9522:
9521:
9518:
9479:
9476:
9475:
9444:
9441:
9440:
9409:
9406:
9405:
9348:
9345:
9344:
9313:
9310:
9309:
9278:
9275:
9274:
9234:
9231:
9230:
9199:
9196:
9195:
9191:
9150:
9136:
9134:
9122:
9116:
9113:
9112:
9060:
9057:
9056:
9024:
9020:
9005:
9001:
8996:
8993:
8992:
8991:
8971:
8967:
8952:
8948:
8943:
8940:
8939:
8938:. For example,
8934:is little-o of
8913:
8869:
8866:
8865:
8828:
8823:
8820:
8819:
8799:
8795:
8778:
8775:
8774:
8748:
8744:
8733:
8709:
8692:
8690:
8687:
8686:
8666:
8662:
8660:
8657:
8656:
8652:
8624:
8585:
8582:
8581:
8543:
8532:
8521:
8510:
8499:
8498:is little-o of
8488:
8473:
8462:
8459:
8452:
8440:
8411:
8408:
8407:
8406:
8380:
8376:
8368:
8365:
8364:
8363:is a subset of
8344:
8340:
8322:
8318:
8310:
8307:
8306:
8283:
8280:
8279:
8278:
8256:
8253:
8252:
8231:
8227:
8223:
8203:
8200:
8199:
8156:
8153:
8152:
8092:
8089:
8088:
8044:
8041:
8040:
8039:
8020:
8016:
8008:
8005:
8004:
7994:quadratic sieve
7988:sub-exponential
7954:
7951:
7950:
7949:
7925:
7921:
7897:
7893:
7856:
7852:
7828:
7824:
7822:
7819:
7818:
7768:
7764:
7756:
7753:
7752:
7690:
7686:
7678:
7675:
7674:
7660:comparison sort
7581:
7578:
7577:
7557:
7556:
7542:
7540:
7513:
7509:
7500:
7499:
7485:
7483:
7470:
7469:
7448:
7444:
7442:
7439:
7438:
7391:
7387:
7376:
7373:
7372:
7329:
7326:
7325:
7317:Searching in a
7285:
7282:
7281:
7280:
7261:
7257:
7249:
7246:
7245:
7232:polylogarithmic
7208:
7205:
7204:
7203:
7184:
7180:
7160:
7157:
7156:
7103:
7100:
7099:
7049:
7046:
7045:
6997:
6994:
6993:
6969:
6965:
6954:
6951:
6950:
6918:
6915:
6914:
6887:
6881:
6859:
6858:
6856:
6853:
6852:
6828:
6824:
6816:
6813:
6812:
6809:
6790:
6775:
6701:
6700:
6688:
6684:
6671:
6656:
6652:
6649:
6648:
6632:
6628:
6624:
6609:
6605:
6598:
6592:
6588:
6542:
6538:
6534:
6516:
6515:
6491:
6487:
6480:
6474:
6470:
6454:
6452:
6449:
6448:
6426:
6423:
6422:
6415:
6394:
6371:
6359:
6332:
6260:
6257:
6256:
6186:
6183:
6182:
6140:
6137:
6107:
6105:
6019:
5997:
5982:
5972:
5949:
5930:
5899:
5878:The statement "
5876:
5871:
5846:
5842:
5828:
5825:
5824:
5807:
5803:
5789:
5786:
5785:
5769:
5766:
5765:
5749:
5746:
5745:
5744:if we restrict
5684:
5681:
5680:
5643:
5640:
5639:
5602:
5599:
5598:
5551:
5548:
5547:
5519:
5509:
5505:
5464:
5461:
5460:
5413:
5410:
5409:
5375:
5365:
5361:
5332:
5329:
5328:
5309:
5307:
5304:
5303:
5281:
5278:
5277:
5255:
5252:
5251:
5232:
5218:
5207:
5198:
5194:
5185:
5181:
5152:
5150:
5147:
5146:
5101:
5073:
5069:
5060:
5056:
5033:
5030:
5029:
5005:
5001:
4996:
4991:
4988:
4987:
4964:
4960:
4955:
4950:
4947:
4946:
4945:can be written
4930:
4927:
4926:
4903:
4899:
4897:
4894:
4893:
4874:
4871:
4870:
4847:
4843:
4841:
4838:
4837:
4821:
4819:
4816:
4815:
4799:
4791:
4780:
4769:
4761:
4750:
4748:
4745:
4744:
4722:
4719:
4718:
4702:
4699:
4698:
4673:
4668:
4656:
4639:
4631:
4623:
4620:
4619:
4599:
4594:
4593:
4591:
4588:
4587:
4571:
4568:
4567:
4551:
4548:
4547:
4536:
4492:
4489:
4488:
4457:
4454:
4453:
4413:
4405:
4397:
4394:
4393:
4389:
4386:
4352:
4349:
4348:
4316:
4312:
4303:
4299:
4297:
4294:
4293:
4261:
4257:
4255:
4252:
4251:
4219:
4215:
4213:
4210:
4209:
4186:
4182:
4173:
4169:
4148:
4144:
4135:
4131:
4129:
4126:
4125:
4105:
4101:
4086:
4082:
4080:
4077:
4076:
4056:
4052:
4037:
4033:
4031:
4028:
4027:
4024:
3970:
3967:
3966:
3945:
3941:
3935:
3931:
3916:
3912:
3906:
3902:
3890:
3886:
3871:
3867:
3864: and
3862:
3853:
3849:
3834:
3830:
3828:
3825:
3824:
3821:
3801:
3797:
3786:
3782:
3774:
3763:
3759:
3755:
3749:
3745:
3741:
3727:
3721:
3712:
3706:
3702:
3696:
3688:
3684:
3669:
3658:
3647:
3643:
3634:
3620:
3617:superpolynomial
3612:
3606:
3602:
3591:
3580:
3568:
3564:
3533:
3523:
3519:
3504:
3500:
3488:
3484:
3472:
3468:
3421:
3418:
3417:
3413:. For example,
3403:
3397:
3394:
3344:
3343:
3329:
3327:
3318:
3314:
3287:
3286:
3272:
3270:
3261:
3257:
3237:
3233:
3231:
3210:
3209:
3201:
3199:
3183:
3177:
3173:
3171:
3158:
3152:
3148:
3146:
3133:
3127:
3123:
3121:
3102:
3096:
3092:
3088:
3086:
3083:
3082:
3075:
3063:
3046:
3041:
3016:
3012:
2989:
2986:
2985:
2959:
2955:
2932:
2929:
2928:
2914:
2907:
2903:
2889:
2875:
2869:
2863:
2848:
2841:
2834:
2825:
2821:
2802:
2798:
2786:
2782:
2775:
2743:
2732:
2696:
2672:
2668:
2657:
2645:
2641:
2629:
2625:
2617:
2615:
2612:
2611:
2597:
2596:
2590:
2586:
2574:
2573:
2567:
2563:
2551:
2547:
2535:
2531:
2519:
2518:
2507:
2501:
2497:
2489:
2480:
2476:
2466:
2461:
2449:
2445:
2433:
2429:
2421:
2417:
2415:
2412:
2411:
2408:
2398:
2391:
2387:
2381:
2378:
2368:
2364:
2361:
2355:
2338:
2334:
2323:
2306:
2304:
2301:
2300:
2281:
2276:. Applying the
2263:
2244:
2225:
2219:
2208:
2202:
2196:
2190:
2186:
2179:
2172:
2168:
2164:
2157:
2150:
2146:
2140:
2121:
2113:
2102:
2088:
2080:
2074:
2071:
2049:
2045:
2037:
2034:
2033:
1990:
1987:
1986:
1969:
1965:
1963:
1960:
1959:
1943:
1940:
1939:
1922:
1921:
1903:
1902:
1882:
1879:
1878:
1858:
1855:
1854:
1838:
1835:
1834:
1803:
1796:
1793:
1792:
1772:
1769:
1768:
1752:
1749:
1748:
1732:
1729:
1728:
1708:
1705:
1704:
1688:
1685:
1684:
1645:
1627:
1623:
1621:
1609:
1603:
1600:
1599:
1574:
1567:
1566:
1548:
1547:
1527:
1524:
1523:
1503:
1500:
1499:
1474:
1471:
1470:
1433:
1416:
1414:
1411:
1410:
1387:
1373:
1365:
1362:
1361:
1360:
1344:
1341:
1340:
1324:
1321:
1320:
1304:
1301:
1300:
1275:
1268:
1267:
1249:
1248:
1228:
1225:
1224:
1202:
1199:
1198:
1182:
1179:
1178:
1162:
1159:
1158:
1138:
1137:
1119:
1118:
1098:
1095:
1094:
1078:
1075:
1074:
1054:
1050:
1039:
1015:
998:
996:
993:
992:
975:
971:
969:
966:
965:
949:
946:
945:
928:
927:
909:
908:
888:
885:
884:
868:
865:
864:
839:
836:
835:
810:
807:
806:
777:
774:
773:
748:
745:
744:
719:
712:
711:
693:
692:
672:
669:
668:
652:
649:
648:
623:
620:
619:
592:
589:
588:
564:
561:
560:
557:
548:
538:
444:
376:False precision
311:
307:
299:
296:
295:
268:
246:
238:
235:
234:
211:
207:
205:
202:
201:
184:
180:
178:
175:
174:
152:
149:
148:
126:
123:
122:
100:
97:
96:
63:
41:
39:
36:
35:
28:
23:
22:
15:
12:
11:
5:
17952:
17942:
17941:
17936:
17931:
17917:
17916:
17911:
17899:
17894:
17889:
17882:
17881:External links
17879:
17878:
17877:
17856:
17835:
17814:
17793:
17772:
17750:
17744:
17720:
17714:
17684:
17678:
17662:
17642:
17639:
17637:
17636:
17619:
17612:
17586:Hardy, G. H.;
17578:
17554:
17539:Landau, Edmund
17530:
17521:
17514:
17496:
17470:(2): 546–563.
17445:
17438:
17418:
17358:) means that 2
17331:
17305:
17298:
17274:such that 0 ≤
17271:
17201:
17183:
17167:
17129:
17117:
17110:
17075:
17013:(April 1985).
16993:
16986:
16956:
16907:
16853:
16841:
16826:
16817:
16799:
16750:
16735:
16715:
16696:
16681:Landau, Edmund
16669:
16649:
16644:
16640:
16636:
16631:
16625:
16602:
16599:
16596:
16593:
16590:
16587:
16584:
16568:
16548:
16545:
16542:
16539:
16536:
16533:
16528:
16510:
16497:
16488:
16434:
16416:
16394:Graham, Ronald
16380:
16362:
16336:
16304:
16289:
16207:
16178:
16162:
16147:Landau, Edmund
16138:
16113:Mohr, Austin.
16105:
16090:Landau, Edmund
16078:
16063:Bachmann, Paul
16050:
16048:
16045:
16044:
16043:
16038:
16033:
16019:
16013:
16007:
16003:
15996:
15988:
15982:
15976:
15969:
15966:
15946:
15945:
15934:
15931:
15928:
15925:
15922:
15919:
15916:
15912:
15908:
15905:
15902:
15879:
15859:
15835:
15826:
15805:
15785:
15762:
15742:
15722:
15702:
15697:
15686:
15685:
15674:
15671:
15668:
15665:
15662:
15659:
15656:
15652:
15648:
15645:
15642:
15622:
15619:
15616:
15613:
15610:
15607:
15603:
15599:
15596:
15593:
15563:
15560:
15557:
15554:
15551:
15548:
15545:
15542:
15539:
15519:
15516:
15513:
15510:
15507:
15504:
15501:
15498:
15495:
15492:
15489:
15486:
15459:
15456:
15453:
15433:
15430:
15427:
15424:
15404:
15401:
15392:
15389:
15369:
15360:
15339:
15336:
15333:
15330:
15327:
15324:
15321:
15318:
15315:
15312:
15309:
15306:
15286:
15283:
15280:
15277:
15274:
15271:
15268:
15265:
15262:
15259:
15256:
15253:
15233:
15230:
15227:
15224:
15221:
15218:
15215:
15212:
15209:
15189:
15169:
15146:
15124:
15120:
15097:
15093:
15070:
15066:
15056:("right") and
15043:
15039:
15014:
14985:
14982:
14923:
14922:
14911:
14908:
14905:
14902:
14899:
14896:
14893:
14890:
14887:
14884:
14880:
14876:
14873:
14870:
14825:
14793:
14790:
14776:
14773:
14770:
14750:
14749:
14738:
14731:
14728:
14725:
14721:
14717:
14714:
14711:
14708:
14705:
14702:
14697:
14693:
14689:
14686:
14683:
14680:
14677:
14674:
14671:
14668:
14665:
14662:
14659:
14656:
14652:
14648:
14645:
14642:
14639:
14636:
14633:
14628:
14624:
14546:
14543:
14540:
14534:
14531:
14525:
14522:
14519:
14514:
14510:
14489:
14484:
14480:
14476:
14470:
14467:
14461:
14456:
14452:
14448:
14343:) =
14322:
14319:
14318:
14317:
14306:
14303:
14300:
14297:
14294:
14291:
14286:
14282:
14278:
14275:
14272:
14269:
14266:
14263:
14260:
14255:
14251:
14247:
14213:
14210:
14205:
14201:
14197:
14194:
14186:
14183:
14180:
14177:
14174:
14171:
14168:
14165:
14162:
14159:
14156:
14153:
14137:
14133:
14118:
14107:
14104:
14101:
14098:
14095:
14092:
14089:
14086:
14065:
14064:
14053:
14047:
14044:
14041:
14038:
14035:
14031:
14028:
14025:
14022:
14019:
14016:
14013:
14010:
14007:
14004:
14001:
13998:
13986:which satisfy
13960:In their book
13957:
13956:Other notation
13954:
13937:
13936:
13922:
13909:
13892:
13891:
13875:
13855:
13800:
13797:
13784:
13764:
13744:
13724:
13704:
13684:
13664:
13644:
13624:
13604:
13584:
13561:
13541:
13538:
13535:
13516:
13513:
13510:
13507:
13504:
13501:
13498:
13495:
13475:
13472:
13469:
13449:
13446:
13443:
13440:
13437:
13434:
13431:
13428:
13408:
13388:
13385:
13382:
13379:
13376:
13373:
13360:
13359:
13348:
13345:
13339:
13336:
13333:
13330:
13325:
13321:
13318:
13315:
13312:
13308:
13300:
13297:
13294:
13290:
13289:lim sup
13279:
13268:
13265:
13262:
13259:
13255:
13252:
13248:
13244:
13241:
13238:
13235:
13231:
13227:
13222:
13218:
13214:
13211:
13208:
13202:
13198:
13194:
13190:
13187:
13184:
13181:
13171:
13154:
13150:
13146:
13135:
13132:
13121:
13118:
13115:
13112:
13109:
13106:
13103:
13100:
13097:
13094:
13091:
13088:
13077:
13076:
13065:
13062:
13056:
13053:
13050:
13047:
13042:
13039:
13036:
13033:
13025:
13022:
13019:
13015:
13004:
12993:
12990:
12987:
12984:
12980:
12977:
12974:
12971:
12968:
12965:
12962:
12957:
12953:
12949:
12946:
12943:
12937:
12933:
12929:
12925:
12922:
12919:
12916:
12906:
12896:
12893:
12882:
12879:
12876:
12873:
12870:
12867:
12864:
12861:
12858:
12855:
12852:
12849:
12838:
12837:
12826:
12823:
12817:
12814:
12811:
12808:
12803:
12800:
12797:
12794:
12786:
12783:
12780:
12776:
12775:lim inf
12765:
12754:
12751:
12748:
12745:
12741:
12738:
12735:
12732:
12729:
12726:
12723:
12718:
12714:
12710:
12707:
12704:
12698:
12694:
12690:
12686:
12683:
12680:
12677:
12667:
12657:
12654:
12643:
12640:
12637:
12634:
12631:
12628:
12625:
12622:
12619:
12616:
12613:
12610:
12599:
12598:
12587:
12584:
12578:
12575:
12572:
12569:
12564:
12561:
12558:
12555:
12547:
12544:
12541:
12537:
12526:
12515:
12512:
12508:
12504:
12501:
12495:
12492:
12489:
12486:
12481:
12478:
12475:
12472:
12465:
12461:
12456:
12452:
12448:
12445:
12442:
12436:
12432:
12428:
12424:
12421:
12418:
12415:
12405:
12403:asymptotically
12393:
12390:
12379:
12376:
12373:
12370:
12367:
12364:
12361:
12358:
12355:
12344:
12343:
12332:
12329:
12326:
12323:
12320:
12317:
12314:
12311:
12308:
12305:
12302:
12299:
12279:
12276:
12273:
12270:
12267:
12264:
12261:
12258:
12255:
12252:
12249:
12246:
12236:
12225:
12222:
12219:
12216:
12210:
12206:
12202:
12199:
12196:
12193:
12190:
12187:
12184:
12181:
12178:
12175:
12169:
12165:
12145:
12140:
12136:
12132:
12129:
12126:
12120:
12116:
12112:
12108:
12105:
12100:
12096:
12092:
12088:
12085:
12080:
12076:
12072:
12062:
12048:
12044:
12021:
12017:
11998:
11995:
11983:
11980:
11977:
11974:
11971:
11968:
11965:
11962:
11959:
11956:
11953:
11950:
11930:
11927:
11924:
11921:
11918:
11915:
11912:
11909:
11906:
11895:
11894:
11883:
11880:
11874:
11871:
11868:
11865:
11860:
11857:
11854:
11851:
11843:
11840:
11837:
11833:
11832:lim sup
11822:
11811:
11808:
11805:
11802:
11798:
11795:
11791:
11787:
11784:
11781:
11778:
11774:
11770:
11765:
11761:
11757:
11754:
11751:
11745:
11741:
11737:
11733:
11730:
11727:
11724:
11714:
11702:
11677:
11673:
11669:
11658:
11655:
11644:
11641:
11638:
11635:
11632:
11629:
11626:
11623:
11620:
11617:
11614:
11611:
11600:
11599:
11588:
11585:
11579:
11576:
11573:
11570:
11565:
11562:
11559:
11556:
11548:
11545:
11542:
11538:
11527:
11516:
11513:
11510:
11507:
11503:
11500:
11496:
11492:
11489:
11486:
11483:
11479:
11475:
11470:
11466:
11462:
11459:
11456:
11450:
11446:
11442:
11438:
11435:
11432:
11429:
11419:
11407:
11389:
11386:
11375:
11372:
11369:
11366:
11363:
11360:
11357:
11354:
11351:
11348:
11345:
11342:
11331:
11330:
11327:
11324:
11321:
11318:
11311:
11308:
11295:
11284:
11283:
11272:
11269:
11266:
11263:
11260:
11257:
11254:
11251:
11248:
11245:
11242:
11239:
11236:
11233:
11230:
11227:
11224:
11221:
11218:
11215:
11212:
11209:
11206:
11203:
11200:
11177:
11161:
11158:
11157:
11156:
11145:
11142:
11139:
11136:
11116:
11113:
11110:
11105:
11101:
11097:
11094:
11091:
11088:
11085:
11082:
11068:
11067:
11056:
11053:
11050:
11047:
11027:
11024:
11021:
11016:
11012:
11008:
11005:
11002:
10999:
10996:
10993:
10979:
10978:
10967:
10964:
10961:
10958:
10938:
10935:
10932:
10929:
10926:
10923:
10920:
10917:
10914:
10911:
10897:
10896:
10885:
10882:
10879:
10876:
10856:
10853:
10850:
10845:
10841:
10837:
10834:
10831:
10828:
10814:
10813:
10802:
10799:
10796:
10793:
10773:
10770:
10767:
10764:
10761:
10758:
10755:
10752:
10737:
10734:
10717:
10714:
10711:
10708:
10705:
10702:
10697:
10693:
10689:
10686:
10683:
10680:
10677:
10657:
10654:
10651:
10648:
10645:
10642:
10637:
10633:
10629:
10626:
10623:
10620:
10617:
10608:(meaning that
10597:
10594:
10591:
10588:
10585:
10582:
10577:
10573:
10569:
10566:
10563:
10560:
10557:
10535:
10531:
10527:
10522:
10518:
10514:
10511:
10486:
10482:
10459:
10455:
10432:
10428:
10405:
10401:
10385:
10384:
10373:
10370:
10364:
10361:
10358:
10355:
10350:
10347:
10344:
10341:
10333:
10330:
10327:
10323:
10322:lim inf
10302:
10299:
10296:
10276:
10273:
10270:
10267:
10264:
10261:
10256:
10252:
10248:
10245:
10242:
10239:
10236:
10225:
10224:
10212:
10209:
10203:
10200:
10197:
10194:
10189:
10186:
10183:
10180:
10172:
10169:
10166:
10162:
10161:lim sup
10141:
10138:
10135:
10115:
10112:
10109:
10106:
10103:
10100:
10095:
10091:
10087:
10084:
10081:
10078:
10075:
10063:, defined as:
10050:
10046:
10023:
10019:
9995:
9992:
9989:
9986:
9983:
9980:
9977:
9974:
9971:
9968:
9965:
9962:
9942:
9939:
9936:
9933:
9930:
9927:
9924:
9921:
9918:
9915:
9912:
9909:
9898:
9897:
9886:
9883:
9879:
9873:
9870:
9867:
9864:
9859:
9856:
9853:
9850:
9844:
9838:
9835:
9832:
9828:
9827:lim sup
9807:
9804:
9801:
9781:
9778:
9775:
9772:
9769:
9766:
9763:
9760:
9757:
9754:
9751:
9748:
9725:
9705:
9702:
9662:
9659:
9639:
9624:
9623:
9611:
9608:
9605:
9585:
9582:
9579:
9576:
9573:
9570:
9567:
9564:
9561:
9558:
9555:
9552:
9529:
9517:
9514:
9513:
9512:
9501:
9498:
9495:
9492:
9489:
9486:
9483:
9463:
9460:
9457:
9454:
9451:
9448:
9428:
9425:
9422:
9419:
9416:
9413:
9394:
9393:
9382:
9379:
9376:
9373:
9370:
9367:
9364:
9361:
9358:
9355:
9352:
9332:
9329:
9326:
9323:
9320:
9317:
9297:
9294:
9291:
9288:
9285:
9282:
9271:
9259:
9256:
9253:
9250:
9247:
9244:
9241:
9238:
9218:
9215:
9212:
9209:
9206:
9203:
9184:
9183:
9171:
9168:
9162:
9159:
9156:
9153:
9148:
9145:
9142:
9139:
9131:
9128:
9125:
9121:
9097:
9094:
9091:
9088:
9085:
9082:
9079:
9076:
9073:
9070:
9067:
9064:
9032:
9027:
9023:
9019:
9016:
9013:
9008:
9004:
9000:
8979:
8974:
8970:
8966:
8963:
8960:
8955:
8951:
8947:
8894:
8893:
8882:
8879:
8876:
8873:
8853:
8850:
8847:
8844:
8841:
8838:
8835:
8831:
8827:
8807:
8802:
8798:
8794:
8791:
8788:
8785:
8782:
8768:
8767:
8756:
8751:
8747:
8743:
8740:
8731:
8728:
8725:
8722:
8719:
8716:
8712:
8708:
8705:
8702:
8699:
8695:
8669:
8665:
8649:
8648:
8637:
8634:
8631:
8626: as
8622:
8619:
8616:
8613:
8610:
8607:
8604:
8601:
8598:
8595:
8592:
8589:
8509:") means that
8451:
8448:
8439:
8436:
8421:
8418:
8415:
8394:
8389:
8386:
8383:
8379:
8375:
8372:
8352:
8347:
8343:
8339:
8336:
8333:
8330:
8325:
8321:
8317:
8314:
8293:
8290:
8287:
8266:
8263:
8260:
8239:
8234:
8230:
8226:
8222:
8219:
8216:
8213:
8210:
8207:
8187:
8184:
8181:
8178:
8175:
8172:
8169:
8166:
8163:
8160:
8151:The statement
8147:
8146:
8142:; enumerating
8134:; finding the
8124:
8119:
8108:
8105:
8102:
8099:
8096:
8085:
8084:
8070:
8065:
8054:
8051:
8048:
8028:
8023:
8019:
8015:
8012:
8001:
8000:
7990:
7981:
7970:
7967:
7964:
7961:
7958:
7934:
7931:
7928:
7924:
7920:
7917:
7914:
7911:
7908:
7905:
7900:
7896:
7892:
7889:
7886:
7883:
7880:
7877:
7874:
7871:
7868:
7865:
7862:
7859:
7855:
7851:
7848:
7845:
7842:
7839:
7836:
7831:
7827:
7815:
7814:
7806:; finding the
7793:
7787:
7776:
7771:
7767:
7763:
7760:
7749:
7748:
7734:insertion sort
7730:selection sort
7714:
7709:
7698:
7693:
7689:
7685:
7682:
7671:
7670:
7652:
7638:
7627:
7624:
7621:
7618:
7615:
7612:
7609:
7606:
7603:
7600:
7597:
7594:
7591:
7588:
7585:
7574:
7573:
7560:
7555:
7552:
7549:
7541:
7539:
7536:
7533:
7530:
7527:
7524:
7521:
7516:
7512:
7508:
7505:
7502:
7501:
7498:
7495:
7492:
7484:
7482:
7479:
7476:
7475:
7473:
7468:
7465:
7462:
7459:
7456:
7451:
7447:
7427:
7416:
7405:
7402:
7399:
7394:
7390:
7386:
7383:
7380:
7369:
7368:
7358:
7353:
7342:
7339:
7336:
7333:
7322:
7321:
7315:
7312:
7301:
7298:
7295:
7292:
7289:
7269:
7264:
7260:
7256:
7253:
7242:
7241:
7234:
7229:
7218:
7215:
7212:
7192:
7187:
7183:
7179:
7176:
7173:
7170:
7167:
7164:
7153:
7152:
7138:
7133:
7122:
7119:
7116:
7113:
7110:
7107:
7096:
7095:
7088:
7085:
7074:
7071:
7068:
7065:
7062:
7059:
7056:
7053:
7042:
7041:
7035:
7030:
7019:
7016:
7013:
7010:
7007:
7004:
7001:
6990:
6989:
6972:
6968:
6964:
6961:
6958:
6947:
6942:
6931:
6928:
6925:
6922:
6911:
6910:
6907:
6904:
6880:
6877:
6862:
6836:
6831:
6827:
6823:
6820:
6808:
6805:
6699:
6696:
6691:
6687:
6683:
6680:
6677:
6674:
6672:
6668:
6665:
6662:
6659:
6655:
6651:
6650:
6647:
6644:
6639:
6635:
6631:
6627:
6623:
6620:
6617:
6612:
6608:
6604:
6601:
6599:
6595:
6591:
6587:
6584:
6581:
6578:
6575:
6572:
6569:
6566:
6563:
6560:
6557:
6554:
6549:
6545:
6541:
6537:
6533:
6530:
6527:
6524:
6521:
6518:
6517:
6514:
6511:
6508:
6505:
6502:
6499:
6494:
6490:
6486:
6483:
6481:
6477:
6473:
6469:
6466:
6463:
6460:
6457:
6456:
6436:
6433:
6430:
6414:
6411:
6331:
6328:
6327:
6326:
6315:
6312:
6309:
6306:
6303:
6300:
6297:
6294:
6291:
6288:
6285:
6282:
6279:
6276:
6273:
6270:
6267:
6264:
6250:
6249:
6238:
6235:
6232:
6229:
6226:
6223:
6220:
6217:
6214:
6211:
6208:
6205:
6202:
6199:
6196:
6193:
6190:
6136:
6133:
5875:
5872:
5870:
5867:
5849:
5845:
5841:
5838:
5835:
5832:
5810:
5806:
5802:
5799:
5796:
5793:
5773:
5753:
5733:
5730:
5727:
5724:
5721:
5718:
5715:
5712:
5709:
5706:
5703:
5700:
5697:
5694:
5691:
5688:
5668:
5665:
5662:
5659:
5656:
5653:
5650:
5647:
5627:
5624:
5621:
5618:
5615:
5612:
5609:
5606:
5583:
5579:
5576:
5572:
5569:
5565:
5562:
5558:
5555:
5544:
5543:
5532:
5529:
5526:
5521: as
5517:
5512:
5508:
5504:
5501:
5498:
5495:
5492:
5489:
5486:
5483:
5480:
5474:
5471:
5468:
5445:
5441:
5438:
5434:
5431:
5427:
5424:
5420:
5417:
5406:
5405:
5394:
5391:
5388:
5385:
5382:
5377: as
5373:
5368:
5364:
5360:
5357:
5354:
5351:
5348:
5345:
5342:
5339:
5336:
5312:
5291:
5288:
5285:
5265:
5262:
5259:
5248:
5247:
5235:
5231:
5228:
5225:
5221:
5217:
5214:
5210:
5206:
5201:
5197:
5193:
5188:
5184:
5180:
5177:
5174:
5171:
5168:
5165:
5162:
5159:
5155:
5132:
5131:
5120:
5117:
5114:
5111:
5108:
5103: as
5099:
5096:
5093:
5090:
5087:
5084:
5081:
5076:
5072:
5068:
5063:
5059:
5055:
5052:
5049:
5046:
5043:
5040:
5037:
5023:Chebyshev norm
5008:
5004:
4999:
4995:
4975:
4972:
4967:
4963:
4958:
4954:
4934:
4914:
4911:
4906:
4902:
4881:
4878:
4858:
4855:
4850:
4846:
4824:
4802:
4798:
4794:
4790:
4787:
4783:
4779:
4776:
4772:
4768:
4764:
4760:
4757:
4753:
4732:
4729:
4726:
4706:
4695:
4694:
4683:
4680:
4676:
4670: as
4666:
4663:
4659:
4655:
4652:
4649:
4646:
4641: is
4638:
4634:
4630:
4627:
4602:
4597:
4575:
4555:
4535:
4532:
4520:
4517:
4514:
4511:
4508:
4505:
4502:
4499:
4496:
4476:
4473:
4470:
4467:
4464:
4461:
4441:
4438:
4435:
4432:
4429:
4426:
4423:
4420:
4416:
4412:
4408:
4404:
4401:
4385:
4382:
4365:
4362:
4359:
4356:
4336:
4333:
4330:
4327:
4324:
4319:
4315:
4311:
4306:
4302:
4281:
4278:
4275:
4272:
4269:
4264:
4260:
4239:
4236:
4233:
4230:
4227:
4222:
4218:
4197:
4194:
4189:
4185:
4181:
4176:
4172:
4168:
4165:
4162:
4159:
4156:
4151:
4147:
4143:
4138:
4134:
4113:
4108:
4104:
4100:
4097:
4094:
4089:
4085:
4064:
4059:
4055:
4051:
4048:
4045:
4040:
4036:
4023:
4020:
4019:
4018:
4007:
4004:
4001:
3998:
3995:
3992:
3989:
3986:
3983:
3980:
3977:
3974:
3964:
3953:
3948:
3944:
3938:
3934:
3930:
3927:
3924:
3919:
3915:
3909:
3905:
3901:
3898:
3893:
3889:
3885:
3882:
3879:
3874:
3870:
3861:
3856:
3852:
3848:
3845:
3842:
3837:
3833:
3820:
3817:
3627:subexponential
3561:
3560:
3549:
3546:
3543:
3540:
3531:
3526:
3522:
3518:
3515:
3512:
3507:
3503:
3499:
3496:
3491:
3487:
3483:
3480:
3475:
3471:
3467:
3464:
3461:
3458:
3455:
3452:
3449:
3446:
3443:
3440:
3437:
3434:
3431:
3428:
3425:
3393:
3390:
3358:
3357:
3342:
3339:
3336:
3328:
3326:
3321:
3317:
3313:
3310:
3307:
3304:
3301:
3298:
3295:
3292:
3290:
3288:
3285:
3282:
3279:
3271:
3269:
3264:
3260:
3256:
3253:
3250:
3245:
3240:
3236:
3230:
3227:
3224:
3221:
3218:
3215:
3213:
3211:
3208:
3200:
3198:
3195:
3189:
3186:
3180:
3176:
3170:
3164:
3161:
3155:
3151:
3145:
3139:
3136:
3130:
3126:
3120:
3117:
3114:
3111:
3108:
3105:
3103:
3099:
3095:
3091:
3090:
3062:
3059:
3036:
3035:
3024:
3019:
3015:
3011:
3008:
3005:
3002:
2999:
2996:
2993:
2979:
2978:
2967:
2962:
2958:
2954:
2951:
2948:
2945:
2942:
2939:
2936:
2774:
2771:
2767:
2766:
2760:
2729:
2728:
2718:
2695:
2692:
2680:
2675:
2671:
2667:
2664:
2660:
2656:
2653:
2648:
2644:
2640:
2637:
2632:
2628:
2624:
2620:
2593:
2589:
2585:
2582:
2579:
2577:
2575:
2570:
2566:
2562:
2559:
2554:
2550:
2546:
2543:
2538:
2534:
2530:
2527:
2524:
2522:
2520:
2517:
2514:
2510:
2504:
2500:
2496:
2492:
2488:
2483:
2479:
2475:
2472:
2469:
2467:
2464:
2460:
2457:
2452:
2448:
2444:
2441:
2436:
2432:
2428:
2424:
2420:
2419:
2406:
2385:
2376:
2359:
2341:
2337:
2333:
2330:
2326:
2322:
2319:
2316:
2313:
2309:
2118:
2117:
2099:
2070:
2067:
2052:
2048:
2044:
2041:
2021:
2018:
2015:
2012:
2009:
2006:
2003:
2000:
1997:
1994:
1972:
1968:
1947:
1925:
1920:
1917:
1914:
1911:
1906:
1901:
1898:
1895:
1892:
1889:
1886:
1862:
1842:
1812:
1809:
1806:
1802:
1801:lim sup
1776:
1756:
1736:
1712:
1692:
1669:
1666:
1663:
1657:
1654:
1651:
1648:
1643:
1639:
1636:
1633:
1630:
1626:
1618:
1615:
1612:
1608:
1607:lim sup
1587:
1584:
1581:
1576: as
1570:
1565:
1562:
1559:
1556:
1551:
1546:
1543:
1540:
1537:
1534:
1531:
1520:limit superior
1507:
1487:
1484:
1481:
1478:
1458:
1455:
1452:
1449:
1446:
1443:
1440:
1436:
1432:
1429:
1426:
1423:
1419:
1397:
1394:
1390:
1386:
1383:
1380:
1376:
1372:
1369:
1348:
1328:
1308:
1288:
1285:
1282:
1277: as
1271:
1266:
1263:
1260:
1257:
1252:
1247:
1244:
1241:
1238:
1235:
1232:
1212:
1209:
1206:
1186:
1166:
1146:
1141:
1136:
1133:
1130:
1127:
1122:
1117:
1114:
1111:
1108:
1105:
1102:
1082:
1062:
1057:
1053:
1049:
1046:
1037:
1034:
1031:
1028:
1025:
1022:
1018:
1014:
1011:
1008:
1005:
1001:
978:
974:
953:
931:
926:
923:
920:
917:
912:
907:
904:
901:
898:
895:
892:
872:
852:
849:
846:
843:
823:
820:
817:
814:
803:absolute value
790:
787:
784:
781:
761:
758:
755:
752:
732:
729:
726:
721: as
715:
710:
707:
704:
701:
696:
691:
688:
685:
682:
679:
676:
656:
636:
633:
630:
627:
596:
568:
556:
553:
495:, meaning the
446:
445:
443:
442:
435:
428:
420:
417:
416:
415:
414:
409:
404:
399:
391:
390:
386:
385:
384:
383:
378:
373:
368:
366:Big O notation
363:
361:Scale analysis
358:
350:
349:
345:
344:
336:
335:
314:
310:
306:
303:
281:
278:
275:
272:
267:
264:
259:
256:
253:
250:
245:
242:
222:
219:
214:
210:
187:
183:
162:
159:
156:
136:
133:
130:
110:
107:
104:
82:
79:
76:
73:
70:
67:
62:
59:
54:
51:
48:
45:
26:
9:
6:
4:
3:
2:
17951:
17940:
17937:
17935:
17932:
17930:
17927:
17926:
17924:
17915:
17912:
17910:
17906:
17903:
17900:
17898:
17895:
17893:
17890:
17888:
17885:
17884:
17866:
17862:
17857:
17845:
17841:
17836:
17824:
17820:
17815:
17803:
17799:
17794:
17782:
17778:
17773:
17769:
17765:
17758:
17757:
17751:
17747:
17741:
17737:
17732:
17731:
17725:
17721:
17717:
17711:
17707:
17706:
17701:
17697:
17693:
17689:
17685:
17681:
17675:
17671:
17667:
17666:Knuth, Donald
17663:
17659:
17655:
17654:
17649:
17645:
17644:
17633:
17629:
17623:
17615:
17609:
17605:
17601:
17597:
17594:. Revised by
17593:
17589:
17588:Wright, E. M.
17582:
17574:
17570:
17569:
17564:
17558:
17550:
17546:
17545:
17540:
17534:
17525:
17517:
17511:
17507:
17500:
17481:
17477:
17473:
17469:
17465:
17464:
17456:
17449:
17441:
17439:9780262046305
17435:
17431:
17430:
17422:
17415:
17413:
17409:
17405:
17401:
17397:
17393:
17389:
17385:
17381:
17377:
17373:
17369:
17365:
17361:
17357:
17353:
17349:
17345:
17341:
17334:
17328:
17324:
17319:
17318:
17309:
17302:
17297:
17293:
17289:
17285:
17281:
17277:
17270:
17266:
17262:
17258:
17254:
17250:
17246:
17242:
17238:
17234:
17230:
17226:
17222:
17218:
17214:
17210:
17204:
17198:
17194:
17187:
17180:
17176:
17171:
17152:
17148:
17141:
17133:
17124:
17122:
17113:
17111:0-262-03293-7
17107:
17103:
17102:
17097:
17093:
17089:
17085:
17079:
17061:
17056:
17051:
17046:
17041:
17036:
17031:
17027:
17023:
17016:
17012:
17008:
17007:Vitányi, Paul
17002:
17000:
16998:
16989:
16983:
16979:
16975:
16971:
16967:
16960:
16941:
16937:
16933:
16929:
16925:
16918:
16911:
16902:
16897:
16892:
16887:
16883:
16879:
16875:
16868:
16866:
16864:
16862:
16860:
16858:
16850:
16845:
16838:
16833:
16831:
16821:
16814:
16813:
16806:
16804:
16788:
16783:
16778:
16774:
16770:
16766:
16759:
16757:
16755:
16746:
16742:
16738:
16732:
16728:
16727:
16719:
16713:
16709:
16706:
16700:
16692:
16688:
16687:
16682:
16676:
16674:
16666:
16663:
16642:
16638:
16629:
16613:-Max-Cut: An
16597:
16594:
16591:
16588:
16585:
16572:
16565:
16562:
16543:
16540:
16537:
16534:
16514:
16507:
16501:
16492:
16485:
16481:
16478:
16462:
16458:
16454:
16453:
16445:
16438:
16423:
16419:
16413:
16409:
16408:
16403:
16399:
16398:Knuth, Donald
16395:
16389:
16387:
16385:
16369:
16365:
16359:
16355:
16354:
16349:
16343:
16341:
16322:
16315:
16308:
16302:
16298:
16293:
16286:
16284:
16280:
16276:
16272:
16268:
16264:
16260:
16256:
16252:
16248:
16244:
16240:
16236:
16232:
16228:
16224:
16220:
16216:
16210:
16204:
16200:
16195:
16194:
16185:
16183:
16173:
16166:
16158:
16154:
16153:
16148:
16142:
16123:
16120:. p. 2.
16116:
16109:
16101:
16097:
16096:
16091:
16085:
16083:
16074:
16070:
16069:
16064:
16058:
16056:
16051:
16042:
16039:
16037:
16034:
16032:can be stated
16031:
16027:
16023:
16020:
16017:
16014:
16011:
16008:
16006:
15999:
15992:
15989:
15986:
15983:
15980:
15977:
15975:
15972:
15971:
15965:
15963:
15959:
15955:
15949:
15932:
15926:
15920:
15917:
15914:
15906:
15903:
15900:
15893:
15892:
15891:
15877:
15857:
15849:
15833:
15824:
15803:
15783:
15774:
15760:
15740:
15720:
15700:
15695:
15672:
15666:
15660:
15657:
15654:
15646:
15643:
15640:
15617:
15611:
15608:
15605:
15597:
15594:
15591:
15584:
15583:
15582:
15580:
15575:
15558:
15552:
15549:
15543:
15537:
15511:
15505:
15496:
15490:
15484:
15476:
15471:
15457:
15454:
15451:
15431:
15428:
15425:
15422:
15402:
15399:
15390:
15387:
15367:
15358:
15331:
15325:
15319:
15316:
15310:
15304:
15278:
15272:
15266:
15263:
15257:
15251:
15228:
15222:
15219:
15213:
15207:
15187:
15167:
15158:
15122:
15095:
15068:
15041:
15028:
15003:
15002:Edmund Landau
14999:
14995:
14991:
14990:Paul Bachmann
14981:
14979:
14975:
14970:
14966:
14960:
14956:
14952:
14948:
14944:
14940:
14936:
14932:
14928:
14906:
14900:
14897:
14891:
14888:
14885:
14874:
14871:
14868:
14861:
14860:
14859:
14857:
14853:
14849:
14845:
14841:
14838:
14834:
14828:
14824:
14820:
14815:
14811:
14807:
14803:
14799:
14789:
14774:
14771:
14768:
14759:
14755:
14736:
14729:
14726:
14723:
14715:
14712:
14709:
14706:
14703:
14695:
14687:
14684:
14681:
14669:
14663:
14660:
14657:
14650:
14646:
14640:
14637:
14634:
14626:
14622:
14614:
14613:
14612:
14611:, defined as
14610:
14608:
14602:
14598:
14593:
14589:
14585:
14581:
14576:
14572:
14568:
14564:
14560:
14541:
14529:
14523:
14520:
14517:
14512:
14508:
14482:
14478:
14465:
14459:
14454:
14450:
14446:
14438:
14432:
14428:
14421:
14417:
14413:
14409:
14405:
14401:
14397:
14392:
14386:
14385:
14379:
14375:
14371:
14367:
14363:
14358:
14354:
14350:
14346:
14342:
14338:
14334:
14330:
14329:
14304:
14298:
14292:
14289:
14284:
14280:
14276:
14273:
14270:
14267:
14264:
14261:
14258:
14253:
14249:
14245:
14238:
14237:
14236:
14234:
14230:
14224:
14211:
14203:
14199:
14195:
14192:
14181:
14175:
14172:
14169:
14163:
14157:
14154:
14151:
14135:
14131:
14116:
14105:
14102:
14096:
14090:
14084:
14076:
14074:
14070:
14051:
14036:
14023:
14017:
14011:
14008:
14002:
13996:
13989:
13988:
13987:
13985:
13981:
13977:
13973:
13969:
13965:
13964:
13953:
13951:
13947:
13943:
13934:
13930:
13926:
13923:
13921:
13917:
13913:
13910:
13908:
13904:
13900:
13897:
13896:
13895:
13888:
13884:
13880:
13876:
13872:
13868:
13864:
13860:
13856:
13852:
13848:
13844:
13840:
13836:
13835:
13834:
13832:
13828:
13824:
13820:
13816:
13812:
13806:
13796:
13782:
13762:
13722:
13702:
13682:
13642:
13622:
13582:
13573:
13539:
13536:
13533:
13514:
13511:
13508:
13505:
13502:
13499:
13496:
13493:
13473:
13470:
13447:
13444:
13441:
13435:
13432:
13429:
13426:
13406:
13386:
13383:
13377:
13371:
13346:
13343:
13334:
13328:
13323:
13316:
13310:
13306:
13292:
13280:
13263:
13257:
13253:
13250:
13239:
13233:
13225:
13220:
13216:
13212:
13209:
13200:
13196:
13188:
13185:
13182:
13172:
13148:
13136:
13133:
13113:
13107:
13098:
13092:
13086:
13079:
13078:
13060:
13051:
13045:
13037:
13031:
13017:
13005:
12988:
12982:
12978:
12975:
12969:
12963:
12960:
12955:
12951:
12947:
12944:
12935:
12931:
12923:
12920:
12917:
12907:
12897:
12894:
12874:
12868:
12862:
12859:
12853:
12847:
12840:
12839:
12824:
12821:
12812:
12806:
12798:
12792:
12778:
12766:
12749:
12743:
12739:
12736:
12730:
12724:
12721:
12716:
12712:
12708:
12705:
12696:
12692:
12684:
12681:
12678:
12668:
12658:
12655:
12635:
12629:
12620:
12614:
12608:
12601:
12600:
12585:
12582:
12573:
12567:
12559:
12553:
12539:
12527:
12513:
12510:
12506:
12502:
12499:
12490:
12484:
12476:
12470:
12463:
12459:
12454:
12450:
12446:
12443:
12434:
12430:
12422:
12419:
12416:
12406:
12404:
12394:
12391:
12374:
12368:
12365:
12359:
12353:
12346:
12345:
12324:
12318:
12312:
12309:
12303:
12297:
12271:
12265:
12259:
12256:
12250:
12244:
12237:
12220:
12214:
12208:
12204:
12200:
12194:
12188:
12185:
12179:
12173:
12167:
12163:
12143:
12138:
12134:
12130:
12127:
12118:
12114:
12106:
12103:
12098:
12094:
12086:
12083:
12078:
12074:
12063:
12046:
12042:
12019:
12015:
11999:
11996:
11975:
11969:
11960:
11954:
11948:
11925:
11919:
11916:
11910:
11904:
11897:
11896:
11878:
11869:
11863:
11855:
11849:
11835:
11823:
11806:
11800:
11796:
11793:
11782:
11776:
11768:
11763:
11759:
11755:
11752:
11743:
11739:
11731:
11728:
11725:
11715:
11700:
11671:
11659:
11656:
11636:
11630:
11624:
11621:
11615:
11609:
11602:
11601:
11586:
11583:
11574:
11568:
11560:
11554:
11540:
11528:
11511:
11505:
11501:
11498:
11487:
11481:
11473:
11468:
11464:
11460:
11457:
11448:
11444:
11436:
11433:
11430:
11420:
11405:
11390:
11387:
11367:
11361:
11355:
11352:
11346:
11340:
11333:
11332:
11328:
11325:
11322:
11319:
11316:
11315:
11307:
11264:
11258:
11252:
11249:
11243:
11237:
11225:
11219:
11210:
11204:
11198:
11191:
11190:
11189:
11167:
11143:
11134:
11111:
11103:
11095:
11092:
11089:
11086:
11083:
11080:
11073:
11072:
11071:
11054:
11045:
11022:
11014:
11006:
11003:
11000:
10997:
10994:
10991:
10984:
10983:
10982:
10965:
10956:
10933:
10924:
10921:
10918:
10915:
10912:
10909:
10902:
10901:
10900:
10883:
10874:
10851:
10843:
10835:
10832:
10829:
10826:
10819:
10818:
10817:
10800:
10791:
10768:
10759:
10756:
10753:
10750:
10743:
10742:
10741:
10733:
10731:
10709:
10703:
10695:
10687:
10681:
10675:
10649:
10643:
10635:
10627:
10621:
10615:
10589:
10583:
10575:
10567:
10561:
10555:
10548:, as well as
10533:
10525:
10520:
10512:
10500:
10484:
10457:
10430:
10403:
10390:
10389:Edmund Landau
10371:
10368:
10359:
10353:
10345:
10339:
10325:
10294:
10268:
10262:
10254:
10246:
10240:
10234:
10227:
10226:
10210:
10207:
10198:
10192:
10184:
10178:
10164:
10133:
10107:
10101:
10093:
10085:
10079:
10073:
10066:
10065:
10064:
10048:
10021:
10007:
9987:
9981:
9975:
9972:
9966:
9960:
9934:
9928:
9919:
9913:
9907:
9884:
9881:
9877:
9868:
9862:
9854:
9848:
9842:
9830:
9799:
9773:
9767:
9758:
9752:
9746:
9739:
9738:
9737:
9715:
9711:
9701:
9699:
9695:
9690:
9688:
9684:
9680:
9676:
9657:
9629:
9609:
9603:
9577:
9571:
9562:
9556:
9550:
9543:
9542:
9541:
9499:
9493:
9487:
9484:
9481:
9458:
9452:
9449:
9446:
9423:
9417:
9414:
9411:
9403:
9402:
9401:
9399:
9380:
9374:
9371:
9368:
9362:
9359:
9356:
9353:
9350:
9327:
9321:
9318:
9315:
9292:
9286:
9283:
9280:
9272:
9254:
9248:
9245:
9242:
9239:
9236:
9213:
9207:
9204:
9201:
9189:
9188:
9187:
9169:
9166:
9157:
9151:
9143:
9137:
9123:
9111:
9110:
9109:
9089:
9083:
9077:
9074:
9068:
9062:
9054:
9050:
9045:
9025:
9021:
9014:
9011:
9006:
9002:
8998:
8972:
8968:
8961:
8958:
8953:
8949:
8945:
8937:
8933:
8929:
8925:
8921:
8916:
8911:
8907:
8903:
8899:
8880:
8871:
8851:
8845:
8839:
8836:
8833:
8829:
8825:
8800:
8796:
8789:
8786:
8783:
8780:
8773:
8772:
8771:
8754:
8749:
8745:
8741:
8738:
8726:
8720:
8717:
8714:
8703:
8697:
8685:
8684:
8683:
8667:
8663:
8629:
8614:
8608:
8602:
8599:
8593:
8587:
8580:
8579:
8578:
8577:. One writes
8576:
8572:
8568:
8564:
8560:
8556:
8550:
8546:
8539:
8535:
8528:
8524:
8517:
8513:
8506:
8502:
8495:
8491:
8484:
8480:
8476:
8469:
8465:
8457:
8447:
8445:
8435:
8419:
8416:
8413:
8387:
8384:
8381:
8377:
8370:
8345:
8337:
8334:
8331:
8323:
8319:
8312:
8291:
8288:
8285:
8264:
8261:
8258:
8237:
8232:
8228:
8224:
8220:
8217:
8211:
8205:
8182:
8179:
8173:
8170:
8164:
8158:
8145:
8141:
8137:
8133:
8129:
8125:
8123:
8120:
8103:
8100:
8094:
8087:
8086:
8083:
8079:
8075:
8071:
8069:
8066:
8052:
8049:
8046:
8021:
8017:
8010:
8003:
8002:
7999:
7995:
7991:
7989:
7985:
7982:
7968:
7965:
7962:
7959:
7956:
7932:
7929:
7926:
7918:
7915:
7912:
7909:
7906:
7898:
7890:
7887:
7884:
7872:
7866:
7863:
7860:
7853:
7849:
7843:
7840:
7837:
7829:
7825:
7817:
7816:
7813:
7809:
7805:
7801:
7797:
7794:
7791:
7788:
7769:
7765:
7758:
7751:
7750:
7747:
7743:
7739:
7735:
7731:
7727:
7723:
7719:
7715:
7713:
7710:
7691:
7687:
7680:
7673:
7672:
7669:
7665:
7661:
7657:
7654:Performing a
7653:
7650:
7646:
7642:
7639:
7622:
7619:
7616:
7613:
7607:
7604:
7598:
7595:
7592:
7589:
7583:
7576:
7575:
7553:
7550:
7547:
7537:
7531:
7528:
7525:
7519:
7514:
7510:
7506:
7503:
7496:
7493:
7490:
7480:
7477:
7471:
7466:
7460:
7454:
7449:
7445:
7436:
7432:
7431:triangulation
7428:
7426:
7423:
7420:
7417:
7400:
7397:
7392:
7388:
7384:
7378:
7371:
7370:
7367:
7363:
7359:
7357:
7354:
7337:
7331:
7324:
7323:
7320:
7316:
7313:
7299:
7296:
7293:
7290:
7287:
7262:
7258:
7251:
7244:
7243:
7239:
7235:
7233:
7230:
7216:
7213:
7210:
7185:
7177:
7174:
7171:
7162:
7155:
7154:
7151:
7150:binomial heap
7147:
7143:
7142:binary search
7139:
7137:
7134:
7117:
7114:
7111:
7105:
7098:
7097:
7093:
7089:
7086:
7069:
7066:
7063:
7060:
7057:
7051:
7044:
7043:
7040:
7036:
7034:
7031:
7011:
7005:
6999:
6992:
6991:
6988:
6970:
6962:
6959:
6948:
6946:
6943:
6926:
6920:
6913:
6912:
6908:
6905:
6902:
6901:
6898:
6896:
6892:
6886:
6876:
6850:
6829:
6825:
6818:
6804:
6801:
6797:
6793:
6786:
6782:
6778:
6773:
6769:
6765:
6761:
6757:
6753:
6749:
6745:
6741:
6737:
6733:
6729:
6725:
6721:
6717:
6697:
6689:
6685:
6678:
6675:
6673:
6663:
6657:
6653:
6645:
6637:
6633:
6629:
6625:
6618:
6615:
6610:
6606:
6602:
6600:
6593:
6582:
6579:
6576:
6570:
6567:
6564:
6558:
6547:
6543:
6539:
6535:
6528:
6525:
6522:
6512:
6506:
6500:
6497:
6492:
6488:
6484:
6482:
6475:
6467:
6464:
6461:
6428:
6420:
6413:Multiple uses
6410:
6408:
6404:
6398:
6390:
6386:
6382:
6378:
6374:
6367:
6363:
6357:
6353:
6349:
6345:
6341:
6337:
6313:
6304:
6298:
6292:
6289:
6283:
6277:
6274:
6268:
6262:
6255:
6254:
6253:
6230:
6224:
6218:
6215:
6209:
6203:
6200:
6194:
6188:
6181:
6180:
6179:
6177:
6173:
6169:
6165:
6159:
6155:
6151:
6147:
6143:
6132:
6130:
6124:
6120:
6114:
6110:
6103:
6099:
6095:
6091:
6087:
6083:
6079:
6075:
6071:
6067:
6063:
6059:
6055:
6052:
6048:
6044:
6038:
6034:
6030:
6026:
6022:
6017:
6012:
6008:
6004:
6000:
5993:
5989:
5985:
5979:
5975:
5970:
5964:
5960:
5956:
5952:
5945:
5941:
5937:
5933:
5928:
5924:
5918:
5914:
5910:
5906:
5902:
5897:
5893:
5889:
5885:
5881:
5866:
5863:
5847:
5836:
5833:
5808:
5797:
5794:
5771:
5751:
5725:
5722:
5719:
5713:
5707:
5704:
5698:
5695:
5692:
5686:
5666:
5663:
5657:
5654:
5651:
5645:
5625:
5622:
5616:
5613:
5610:
5604:
5595:
5581:
5577:
5570:
5563:
5556:
5524:
5510:
5506:
5499:
5496:
5490:
5487:
5484:
5478:
5472:
5469:
5459:
5458:
5457:
5443:
5439:
5432:
5425:
5418:
5386:
5383:
5380:
5366:
5362:
5355:
5352:
5346:
5343:
5340:
5334:
5327:
5326:
5325:
5289:
5286:
5283:
5263:
5260:
5257:
5229:
5226:
5223:
5215:
5212:
5199:
5195:
5191:
5186:
5182:
5175:
5169:
5166:
5163:
5157:
5145:
5144:
5143:
5141:
5137:
5112:
5109:
5106:
5094:
5091:
5088:
5082:
5079:
5074:
5070:
5066:
5061:
5057:
5053:
5047:
5044:
5041:
5035:
5028:
5027:
5026:
5024:
4973:
4970:
4932:
4912:
4909:
4904:
4900:
4879:
4876:
4856:
4853:
4848:
4844:
4785:
4777:
4774:
4755:
4730:
4727:
4724:
4704:
4650:
4644:
4625:
4618:
4617:
4616:
4600:
4573:
4553:
4545:
4541:
4531:
4518:
4512:
4506:
4503:
4500:
4497:
4494:
4471:
4465:
4462:
4459:
4436:
4430:
4427:
4421:
4418:
4410:
4399:
4381:
4379:
4360:
4354:
4331:
4325:
4322:
4317:
4313:
4309:
4304:
4300:
4276:
4270:
4267:
4262:
4258:
4234:
4228:
4225:
4220:
4216:
4187:
4183:
4179:
4174:
4170:
4157:
4154:
4149:
4145:
4141:
4136:
4132:
4106:
4102:
4095:
4092:
4087:
4083:
4057:
4053:
4046:
4043:
4038:
4034:
4002:
3999:
3993:
3990:
3984:
3978:
3975:
3972:
3965:
3946:
3942:
3936:
3932:
3925:
3922:
3917:
3913:
3907:
3903:
3891:
3887:
3880:
3877:
3872:
3868:
3854:
3850:
3843:
3840:
3835:
3831:
3823:
3822:
3816:
3812:
3808:
3804:
3793:
3789:
3780:
3770:
3766:
3752:
3737:
3733:
3730:
3724:
3718:
3715:
3709:
3699:
3692:
3681:
3677:
3673:
3665:
3661:
3654:
3650:
3640:
3637:
3632:
3628:
3623:
3618:
3609:
3598:
3594:
3587:
3583:
3578:
3574:
3547:
3538:
3524:
3520:
3513:
3510:
3505:
3501:
3497:
3494:
3489:
3485:
3481:
3478:
3473:
3465:
3462:
3459:
3453:
3450:
3447:
3444:
3441:
3438:
3435:
3429:
3423:
3416:
3415:
3414:
3410:
3406:
3400:
3389:
3387:
3383:
3379:
3375:
3371:
3367:
3363:
3340:
3334:
3319:
3315:
3308:
3305:
3302:
3299:
3296:
3293:
3291:
3283:
3277:
3262:
3258:
3251:
3248:
3243:
3238:
3234:
3228:
3225:
3222:
3219:
3216:
3214:
3206:
3203:for all
3196:
3193:
3187:
3184:
3178:
3174:
3168:
3162:
3159:
3153:
3149:
3143:
3137:
3134:
3128:
3124:
3118:
3115:
3112:
3109:
3106:
3104:
3097:
3093:
3081:
3080:
3079:
3073:
3068:
3058:
3056:
3052:
3044:
3017:
3013:
3006:
3003:
2997:
2991:
2984:
2983:
2982:
2960:
2956:
2949:
2946:
2940:
2934:
2927:
2926:
2925:
2921:
2917:
2913:
2900:
2896:
2892:
2886:
2883:) = 1,000,000
2882:
2878:
2872:
2866:
2861:
2857:
2852:
2845:
2837:
2832:
2828:
2817:
2813:
2809:
2805:
2796:
2779:
2770:
2764:
2763:infinitesimal
2761:
2758:
2755:
2754:
2753:
2750:
2746:
2739:
2735:
2727:
2723:
2719:
2717:
2713:
2712:Taylor series
2709:
2705:
2701:
2700:
2699:
2691:
2678:
2673:
2669:
2665:
2662:
2654:
2651:
2646:
2642:
2638:
2635:
2630:
2626:
2622:
2591:
2587:
2583:
2580:
2578:
2568:
2564:
2560:
2557:
2552:
2548:
2544:
2541:
2536:
2532:
2528:
2525:
2523:
2515:
2512:
2502:
2498:
2494:
2486:
2481:
2477:
2473:
2470:
2468:
2458:
2455:
2450:
2446:
2442:
2439:
2434:
2430:
2426:
2405:
2401:
2394:
2384:
2375:
2371:
2358:
2339:
2335:
2331:
2328:
2317:
2311:
2296:
2292:
2288:
2284:
2279:
2274:
2270:
2266:
2259:
2255:
2251:
2247:
2240:
2236:
2232:
2228:
2222:
2215:
2211:
2205:
2199:
2193:
2183:
2176:
2161:
2154:
2143:
2136:
2132:
2128:
2124:
2109:
2105:
2100:
2095:
2091:
2086:
2085:
2084:
2077:
2066:
2050:
2046:
2042:
2039:
2016:
2010:
2007:
2004:
1998:
1992:
1970:
1966:
1945:
1915:
1909:
1899:
1896:
1890:
1884:
1876:
1860:
1840:
1831:
1829:
1810:
1804:
1790:
1774:
1754:
1734:
1726:
1725:cluster point
1723:or not) is a
1690:
1683:
1667:
1661:
1652:
1646:
1641:
1634:
1628:
1624:
1616:
1610:
1585:
1579:
1560:
1554:
1544:
1541:
1535:
1529:
1521:
1505:
1482:
1476:
1456:
1450:
1444:
1441:
1438:
1427:
1421:
1395:
1392:
1384:
1381:
1378:
1370:
1367:
1346:
1326:
1306:
1286:
1280:
1261:
1255:
1245:
1242:
1236:
1230:
1210:
1207:
1204:
1184:
1164:
1144:
1131:
1125:
1115:
1112:
1106:
1100:
1080:
1060:
1055:
1051:
1047:
1044:
1032:
1026:
1023:
1020:
1009:
1003:
976:
972:
951:
921:
915:
905:
902:
896:
890:
870:
847:
841:
818:
812:
804:
785:
779:
756:
750:
724:
705:
699:
689:
686:
680:
674:
667:. One writes
654:
631:
625:
617:
613:
610:
594:
586:
582:
566:
552:
545:
541:
535:
533:
529:
523:
521:
517:
513:
509:
505:
500:
498:
494:
493:
488:
484:
480:
479:Edmund Landau
476:
475:Paul Bachmann
472:
468:
464:
460:
456:
454:
441:
436:
434:
429:
427:
422:
421:
419:
418:
413:
410:
408:
405:
403:
400:
398:
397:Approximation
395:
394:
393:
392:
388:
387:
382:
379:
377:
374:
372:
371:Curve fitting
369:
367:
364:
362:
359:
357:
354:
353:
352:
351:
347:
346:
342:
338:
337:
333:
332:
312:
308:
304:
301:
276:
270:
265:
262:
254:
248:
243:
240:
220:
217:
212:
208:
185:
181:
160:
157:
154:
134:
131:
128:
102:
74:
68:
60:
57:
49:
43:
32:
19:
17871:December 16,
17869:. Retrieved
17864:
17850:December 16,
17848:. Retrieved
17843:
17829:December 16,
17827:. Retrieved
17822:
17808:December 16,
17806:. Retrieved
17801:
17787:December 16,
17785:. Retrieved
17780:
17755:
17729:
17704:
17669:
17652:
17648:Hardy, G. H.
17631:
17627:
17622:
17604:Andrew Wiles
17591:
17581:
17575:. p. 2.
17567:
17563:Hardy, G. H.
17557:
17548:
17543:
17533:
17524:
17505:
17499:
17487:. Retrieved
17467:
17461:
17448:
17428:
17421:
17411:
17407:
17403:
17399:
17395:
17391:
17387:
17383:
17379:
17375:
17371:
17367:
17363:
17359:
17355:
17351:
17347:
17343:
17339:
17336:
17316:
17308:
17295:
17291:
17287:
17283:
17279:
17275:
17268:
17264:
17260:
17256:
17252:
17248:
17244:
17240:
17236:
17232:
17228:
17224:
17220:
17216:
17212:
17208:
17206:
17192:
17186:
17178:
17170:
17158:. Retrieved
17146:
17132:
17100:
17078:
17067:. Retrieved
17028:(4): 56–59.
17025:
17021:
16969:
16959:
16947:. Retrieved
16927:
16923:
16910:
16884:(2): 18–24.
16881:
16877:
16844:
16820:
16810:
16791:. Retrieved
16772:
16768:
16725:
16718:
16699:
16690:
16685:
16664:
16662:Algorithmica
16661:
16571:
16563:
16560:
16513:
16505:
16500:
16491:
16468:. Retrieved
16456:
16450:
16437:
16426:. Retrieved
16406:
16372:. Retrieved
16352:
16328:. Retrieved
16307:
16292:
16282:
16278:
16274:
16270:
16266:
16262:
16258:
16254:
16250:
16246:
16242:
16238:
16234:
16230:
16226:
16222:
16218:
16214:
16212:
16192:
16171:
16165:
16156:
16151:
16141:
16129:. Retrieved
16108:
16099:
16094:
16072:
16067:
16001:
15994:
15960:. The digit
15950:
15947:
15816:(as well as
15775:
15687:
15578:
15576:
15530:for Hardy's
15475:Donald Knuth
15472:
15159:
15026:
14993:
14987:
14977:
14973:
14968:
14964:
14958:
14954:
14950:
14946:
14942:
14938:
14934:
14930:
14925:which is an
14924:
14847:
14843:
14839:
14826:
14822:
14818:
14809:
14805:
14801:
14795:
14760:in terms of
14751:
14606:
14603:
14596:
14591:
14587:
14583:
14579:
14573:because the
14566:
14562:
14558:
14436:
14430:
14426:
14419:
14415:
14411:
14407:
14403:
14399:
14395:
14390:
14383:
14377:
14373:
14369:
14365:
14361:
14352:
14348:
14344:
14340:
14336:
14332:
14326:
14324:
14232:
14228:
14225:
14077:
14072:
14068:
14066:
13983:
13961:
13959:
13949:
13945:
13941:
13938:
13932:
13928:
13924:
13919:
13915:
13911:
13906:
13902:
13898:
13893:
13886:
13882:
13878:
13870:
13866:
13862:
13858:
13850:
13846:
13842:
13838:
13830:
13826:
13822:
13818:
13810:
13808:
13595:, big Theta
13574:
13363:
12398:is equal to
11323:Description
11285:
11166:Donald Knuth
11163:
11069:
10980:
10898:
10815:
10739:
10501:
10386:
10008:
9899:
9707:
9691:
9686:
9685:, and where
9682:
9678:
9674:
9627:
9625:
9519:
9398:transitivity
9395:
9185:
9052:
9048:
9046:
8935:
8931:
8927:
8923:
8919:
8914:
8909:
8905:
8902:at least one
8901:
8895:
8769:
8650:
8574:
8570:
8566:
8565:, such that
8563:real numbers
8558:
8554:
8548:
8544:
8537:
8533:
8526:
8522:
8515:
8511:
8504:
8500:
8493:
8489:
8482:
8478:
8474:
8467:
8463:
8460:
8456:Omar Vizquel
8443:
8441:
8150:
8126:Solving the
7792:or algebraic
7717:
7648:
7644:
7641:linearithmic
7424:
7418:
7366:ripple carry
7361:
6987:lookup table
6894:
6890:
6888:
6810:
6799:
6795:
6791:
6784:
6780:
6776:
6767:
6763:
6759:
6758:) such that
6755:
6751:
6747:
6743:
6739:
6735:
6731:
6727:
6723:
6719:
6715:
6418:
6416:
6406:
6402:
6396:
6388:
6384:
6380:
6376:
6372:
6365:
6361:
6355:
6351:
6347:
6343:
6339:
6333:
6251:
6175:
6171:
6167:
6163:
6157:
6153:
6149:
6145:
6141:
6138:
6128:
6122:
6118:
6112:
6108:
6104:) such that
6101:
6097:
6093:
6089:
6085:
6081:
6077:
6073:
6069:
6065:
6061:
6057:
6053:
6046:
6042:
6036:
6032:
6028:
6024:
6020:
6016:set notation
6013:
6006:
6002:
5998:
5991:
5987:
5983:
5977:
5973:
5962:
5958:
5954:
5950:
5948:is true but
5943:
5939:
5935:
5931:
5916:
5912:
5908:
5904:
5900:
5895:
5891:
5887:
5883:
5879:
5877:
5864:
5596:
5545:
5407:
5249:
5139:
5135:
5133:
5021:denotes the
4696:
4543:
4539:
4537:
4387:
4025:
3810:
3806:
3802:
3791:
3787:
3778:
3768:
3764:
3750:
3744:, replacing
3735:
3731:
3728:
3722:
3716:
3713:
3707:
3701:, replacing
3697:
3693:
3679:
3675:
3671:
3663:
3659:
3652:
3648:
3641:
3635:
3626:
3621:
3616:
3607:
3596:
3592:
3585:
3581:
3576:
3572:
3562:
3408:
3404:
3398:
3395:
3385:
3381:
3377:
3373:
3369:
3365:
3361:
3359:
3064:
3039:
3037:
2980:
2919:
2915:
2911:
2898:
2894:
2890:
2884:
2880:
2876:
2870:
2864:
2856:coefficients
2850:
2843:
2835:
2826:
2815:
2811:
2807:
2803:
2792:
2768:
2765:asymptotics.
2751:
2744:
2737:
2733:
2730:
2697:
2403:
2399:
2392:
2382:
2373:
2369:
2367:and for all
2356:
2294:
2290:
2286:
2282:
2272:
2268:
2264:
2257:
2253:
2249:
2245:
2238:
2234:
2230:
2226:
2220:
2213:
2209:
2203:
2197:
2191:
2181:
2174:
2159:
2152:
2141:
2134:
2130:
2126:
2122:
2119:
2107:
2103:
2093:
2089:
2075:
2072:
1832:
772:is big O of
616:real numbers
558:
543:
539:
536:
527:
524:
501:
490:
486:
482:
452:
450:
449:
365:
233:) such that
16878:SIGACT News
15415:means that
15160:The symbol
14852:derivatives
14833:filter base
14758:exponential
14575:growth-rate
8136:determinant
8068:exponential
7808:determinant
7726:bubble sort
7429:Performing
7136:logarithmic
6807:Typesetting
6334:Suppose an
6041:(read as: "
5874:Equals sign
4378:convex cone
3577:lower-order
3051:Equals sign
2922:(1,000,000)
2840:, the term
2759:asymptotics
2704:mathematics
1682:limit point
883:. That is,
532:upper bound
17923:Categories
17489:2022-02-03
17290:) for all
17069:2017-03-14
16930:(2): 180.
16793:2017-03-14
16470:2021-09-05
16459:(6): 687.
16428:2016-09-23
16374:2021-09-15
16330:2015-04-23
15581:notation)
14754:polynomial
14604:Also, the
14582:is always
13715:, Hardy's
12901:dominates
9400:relation:
8682:such that
7984:L-notation
7790:polynomial
7668:merge sort
6018:and write
5142:such that
4743:such that
3625:is called
3615:is called
3567:, then as
3392:Properties
3078:is small:
3067:error term
2874:. Even if
1985:such that
1223:): we say
991:such that
17378:), where
17098:(2001) .
17030:CiteSeerX
16936:0988-3754
16745:676697295
16630:∗
16595:−
16541:
15911:⟺
15904:≪
15858:≪
15834:−
15825:≍
15804:≺
15784:≼
15761:≺
15741:≼
15721:≪
15701:≺
15696:≺
15651:⟺
15644:≺
15602:⟺
15595:≼
15550:≍
15500:Θ
15426:∼
15400:−
15391:≍
15368:−
15359:≍
15220:≍
15188:≍
15168:∼
15145:Ω
15123:−
15119:Ω
15092:Ω
15065:Ω
15038:Ω
15013:Ω
14898:∈
14889:−
14879:⟺
14872:∼
14842:and
14772:
14730:α
14727:−
14713:
14707:
14696:α
14685:
14635:α
14533:~
14518:
14469:~
14389:for some
14357:shorthand
14196:≥
14170:≤
14155:≤
14145:such that
14075:), where
14043:∞
14040:→
13972:Leiserson
13783:ω
13763:∼
13743:Ω
13723:≍
13663:Ω
13643:ω
13615:, little
13603:Θ
13560:Ω
13534:≥
13506:≈
13500:≤
13474:ω
13468:Ω
13445:∼
13439:Θ
13299:∞
13296:→
13251:≥
13226::
13207:∃
13193:∀
13180:∃
13102:Ω
13064:∞
13024:∞
13021:→
12961::
12942:∀
12928:∃
12915:∀
12863:ω
12785:∞
12782:→
12737:≥
12722::
12703:∀
12689:∃
12676:∃
12624:Ω
12546:∞
12543:→
12514:ε
12500:−
12460::
12441:∀
12427:∃
12417:ε
12414:∀
12366:∼
12201:≤
12186:≤
12144::
12125:∀
12111:∃
12091:∃
12071:∃
11964:Θ
11917:≍
11882:∞
11842:∞
11839:→
11794:≤
11769::
11750:∀
11736:∃
11723:∃
11547:∞
11544:→
11499:≤
11474::
11455:∀
11441:∃
11428:∀
11317:Notation
11294:Ω
11235:⇔
11214:Ω
11176:Ω
11141:∞
11138:→
11104:−
11100:Ω
11084:
11052:∞
11049:→
11011:Ω
10995:
10963:∞
10960:→
10928:Ω
10913:
10881:∞
10878:→
10844:±
10840:Ω
10830:
10798:∞
10795:→
10763:Ω
10754:
10696:−
10692:Ω
10632:Ω
10576:±
10572:Ω
10534:−
10530:Ω
10517:Ω
10510:Ω
10485:−
10481:Ω
10454:Ω
10427:Ω
10400:Ω
10332:∞
10329:→
10301:∞
10298:→
10251:Ω
10171:∞
10168:→
10140:∞
10137:→
10090:Ω
10045:Ω
10018:Ω
9923:Ω
9837:∞
9834:→
9806:∞
9803:→
9762:Ω
9724:Ω
9661:∞
9658:−
9638:∞
9607:→
9566:Ω
9528:Ω
9372:⋅
9354:⋅
9240:⋅
9130:∞
9127:→
9012:≠
8904:constant
8878:∞
8875:→
8742:≥
8718:ε
8715:≤
8636:∞
8633:→
8487:" (read "
8414:ε
8388:ε
8335:
8122:factorial
7963:α
7933:α
7930:−
7916:
7910:
7899:α
7888:
7838:α
7746:tree sort
7742:Shellsort
7738:quicksort
7712:quadratic
7617:
7596:
7529:
7520:
7515:∗
7494:≤
7455:
7450:∗
7398:
7393:∗
7175:
7115:
7067:
7061:
7006:α
6960:−
6875:instead.
6580:
6559:⋅
6435:∞
6432:→
6336:algorithm
6275:−
6178:). Thus,
6117:| ≤
6064:))", or "
5927:de Bruijn
5840:∞
5801:∞
5582:⋯
5575:∀
5568:∃
5561:∃
5554:∀
5531:∞
5528:→
5473::
5467:∀
5444:⋯
5437:∀
5430:∀
5423:∃
5416:∃
5393:∞
5390:→
5287:≥
5261:≥
5213:≤
5176:−
5119:∞
5116:→
5007:∞
5003:‖
4994:‖
4971:≥
4966:∞
4962:‖
4953:‖
4925:for some
4910:≥
4869:for some
4854:≥
4775:≤
4682:∞
4679:→
4615:. We say
4498:⋅
4419:⋅
4323:∈
3976:⋅
3900:⇒
3571:tends to
3545:∞
3542:→
3463:
3445:
3338:→
3281:→
3197:⋯
3040:order of
3004:∈
2908:1,000,000
2663:≤
2636:−
2526:≤
2471:≤
2440:−
2329:≤
2171:, namely
2043:≥
2005:≤
1808:→
1711:∞
1703:(whether
1665:∞
1614:→
1583:→
1439:≤
1396:δ
1382:−
1307:δ
1284:→
1048:≥
1021:≤
801:" if the
731:∞
728:→
609:unbounded
465:when the
305:≥
294:whenever
263:≤
244:≤
109:∞
106:→
17905:Archived
17726:(1997).
17650:(1910).
17565:(1910).
17541:(1909).
17480:Archived
17160:14 March
17151:Archived
17060:Archived
17055:11700420
16949:14 March
16940:Archived
16787:Archived
16708:Archived
16683:(1909).
16480:Archived
16461:Archived
16422:Archived
16404:(1994).
16368:Archived
16350:(1958).
16321:Archived
16213:Because
16149:(1909).
16122:Archived
16092:(1909).
16065:(1894).
15968:See also
15455:≠
15380:, where
15200:, where
14609:notation
14594:and any
13695:, small
11164:In 1976
11096:≠
11070:however
10899:We have
10740:We have
9708:In 1914
9673:, where
8405:for any
7800:matching
7664:heapsort
7544:if
7487:if
7437:, where
7422:log-star
7319:k-d tree
6945:constant
6909:Example
6903:Notation
6330:Example
5967:is not.
4986:, where
4814:for all
4487:, then
3611:for any
3573:infinity
3535:as
3331:as
3274:as
2757:infinite
2032:for all
1197:(often,
467:argument
463:function
455:notation
348:Concepts
17366:+ 1 = 2
17346:+ 1 = 2
17255:)) = {
16901:5230246
16775:: 225.
15954:omicron
14972:is not
14961:), but
14945:= 1 if
14424:. When
10472:became
10418:became
5679:, then
5546:(i.e.,
5408:(i.e.,
3819:Product
3756:2 = (2)
3384:| when
3372:− (1 +
2069:Example
585:complex
492:Ordnung
147:(e.g.,
17742:
17738:–228.
17712:
17676:
17610:
17512:
17436:
17329:
17199:
17108:
17052:
17032:
16984:
16934:
16898:
16743:
16733:
16414:
16360:
16205:
16131:7 June
15713:, nor
14846:. The
14599:> 0
14414:) log
14355:)) as
14333:soft-O
14331:(read
14149:
14141:
14128:
14120:
14114:
14049:
13976:Rivest
13968:Cormen
13885:) = Θ(
13825:) = 73
9650:, or
9626:where
8076:using
7744:, and
7356:linear
6847:. In
6379:) = 55
6106:|
5929:says,
5476:
3779:digits
3754:gives
2163:, and
1791:, the
618:, and
612:subset
547:, and
200:(e.g.,
173:) and
17760:(PDF)
17547:[
17483:(PDF)
17458:(PDF)
17402:) = 3
17154:(PDF)
17143:(PDF)
17063:(PDF)
17050:S2CID
17018:(PDF)
16943:(PDF)
16920:(PDF)
16896:S2CID
16689:[
16464:(PDF)
16447:(PDF)
16324:(PDF)
16317:(PDF)
16301:p. 53
16155:[
16125:(PDF)
16118:(PDF)
16098:[
16071:[
15958:Omega
14957:is Θ(
14933:is Θ(
13980:Stein
13815:tight
11320:Name
9900:Thus
9474:then
9343:then
9270:, and
9229:then
8910:every
8138:with
8132:poset
7810:with
6750:) =
5969:Knuth
5886:) is
4836:with
4376:is a
4292:then
4124:then
3809:(log
3790:(log
3748:with
3662:(log(
3651:(log
2888:, if
2860:order
2838:= 500
2820:. As
2810:) = 4
2694:Usage
2402:>
2372:>
2252:) = 6
2129:) = 6
1359:with
542:, Ω,
461:of a
17873:2006
17852:2006
17831:2006
17810:2006
17789:2006
17740:ISBN
17710:ISBN
17674:ISBN
17608:ISBN
17598:and
17510:ISBN
17434:ISBN
17327:ISBN
17282:) ≤
17267:and
17197:ISBN
17162:2017
17106:ISBN
16982:ISBN
16951:2017
16932:ISSN
16741:OCLC
16731:ISBN
16412:ISBN
16358:ISBN
16273:) =
16233:) ∈
16203:ISBN
16133:2014
15962:zero
15796:and
15753:and
15297:and
14949:and
14854:and
14837:nets
14804:and
14756:and
14402:) =
14382:log
14368:) =
14359:for
13978:and
13865:) =
13845:) =
13829:+ 22
13540:>
13494:<
13384:>
13344:>
13213:>
13186:>
12976:>
12948:>
12921:>
12822:>
12709:>
12682:>
12511:<
12447:>
12420:>
12290:and
12131:>
12104:>
12084:>
11879:<
11756:>
11729:>
11461:>
11434:>
10668:and
10445:and
10369:<
10208:>
10036:and
9882:>
9712:and
9677:and
9439:and
9308:and
8990:but
8818:and
8442:Big
8417:>
8289:>
8277:and
8262:>
8050:>
7966:<
7960:<
7802:for
7732:and
7666:and
7647:log
7551:>
7297:<
7291:<
7214:>
7146:tree
6906:Name
6798:) =
6738:) =
6724:some
6399:+ 10
6368:+ 10
6148:) +
6027:) ∈
5996:and
5957:) =
5938:) =
5907:) =
5764:and
5638:and
5138:and
4728:>
4717:and
4566:and
4538:Big
4388:Let
4250:and
4075:and
3734:= O(
3687:and
3678:log
3674:) =
3670:log(
3590:and
2912:viz.
2897:) =
2831:term
2395:= 13
2390:and
2289:) =
2271:) =
2262:and
2233:) =
2189:and
1958:and
1853:and
1747:and
1662:<
1393:<
1371:<
1319:and
581:real
559:Let
451:Big
132:>
18:O(1)
17861:"Θ"
17840:"ω"
17819:"Ω"
17764:doi
17736:226
17472:doi
17362:+ 3
17342:+ 3
17239:of
17231:of
17040:doi
16974:doi
16886:doi
16777:doi
16538:log
14980:).
14601:).
14509:log
14124:and
13014:lim
12536:lim
11537:lim
11127:as
11081:sin
11038:as
10992:sin
10949:as
10910:sin
10867:as
10827:sin
10784:as
10751:sin
10313:if
10287:as
10152:if
10126:as
9818:if
9792:as
9596:as
9404:if
9273:if
9190:if
9120:lim
9047:If
8472:is
8332:log
7996:or
7986:or
7614:log
7593:log
7526:log
7511:log
7446:log
7389:log
7172:log
7112:log
7064:log
7058:log
6849:TeX
6716:any
6577:log
6364:+ 2
5784:to
5594:).
5276:or
4164:max
4026:If
4022:Sum
3777:of
3705:by
3460:log
3442:log
2981:or
2868:or
2818:+ 2
2814:− 2
2747:(·)
2720:In
2714:or
2702:In
2610:so
2388:= 1
2260:+ 5
2256:− 2
2137:+ 5
2133:− 2
2101:If
2087:If
1598:if
1469:As
805:of
583:or
502:In
485:or
95:as
17925::
17863:.
17842:.
17821:.
17800:.
17779:.
17698:;
17694:;
17690:;
17656:.
17571:.
17478:.
17468:39
17466:.
17460:.
17370:+
17350:+
17335:.
17325:.
17323:49
17294:≥
17284:cg
17205:.
17120:^
17094:;
17090:;
17086:;
17058:.
17048:.
17038:.
17026:16
17024:.
17020:.
17009:;
16996:^
16980:.
16968:.
16938:.
16928:23
16926:.
16922:.
16894:.
16880:.
16876:.
16856:^
16829:^
16802:^
16785:.
16773:37
16771:.
16767:.
16753:^
16739:.
16672:^
16665:80
16564:57
16457:45
16455:.
16449:.
16420:.
16400:;
16396:;
16383:^
16366:.
16339:^
16319:.
16299:,
16211:.
16201:.
16199:45
16181:^
16081:^
16054:^
16000:,
15993::
15470:.
14996:("
14967:−
14941:/
14821:→
14769:ln
14710:ln
14704:ln
14682:ln
14422:))
14380:)
13974:,
13970:,
13966:,
12061:)
11713:)
11418:)
10732:.
10499:.
10372:0.
10006:.
9885:0.
8485:))
7913:ln
7907:ln
7885:ln
7740:,
7728:,
7662:;
7240:.
6803:.
6779:=
6762:=
6447::
6383:+
6360:55
6160:))
6119:Cg
6049:)
6039:))
6001:=
5986:=
5976:=
5919:))
5862:.
4380:.
3815:.
3805:=
3751:cn
3708:cn
3666:))
3639:.
3376:+
3057:.
2910:,
2666:13
2584:13
2410::
2158:−2
2156:,
2065:.
1522::
499:.
477:,
17875:.
17854:.
17833:.
17812:.
17791:.
17770:.
17766::
17748:.
17718:.
17682:.
17660:.
17632:n
17630:(
17628:G
17616:.
17518:.
17492:.
17474::
17442:.
17412:n
17410:(
17408:θ
17404:n
17400:n
17398:(
17396:f
17392:n
17390:(
17388:θ
17384:n
17382:(
17380:f
17376:n
17374:(
17372:f
17368:n
17364:n
17360:n
17356:n
17354:(
17352:θ
17348:n
17344:n
17340:n
17301:}
17299:0
17296:n
17292:n
17288:n
17286:(
17280:n
17278:(
17276:f
17272:0
17269:n
17265:c
17261:n
17259:(
17257:f
17253:n
17251:(
17249:g
17247:(
17245:O
17241:n
17237:g
17233:n
17229:g
17225:n
17223:(
17221:g
17219:(
17217:O
17213:n
17211:(
17209:g
17179:O
17164:.
17114:.
17072:.
17042::
16990:.
16976::
16904:.
16888::
16882:8
16796:.
16779::
16747:.
16648:)
16643:p
16639:2
16635:(
16624:O
16601:)
16598:k
16592:n
16589:,
16586:k
16583:(
16547:)
16544:N
16535:N
16532:(
16527:O
16486:)
16475:(
16473:.
16431:.
16377:.
16333:.
16283:n
16281:(
16279:g
16277:(
16275:θ
16271:n
16269:(
16267:f
16263:n
16261:(
16259:g
16257:(
16255:θ
16251:n
16249:(
16247:f
16243:n
16241:(
16239:g
16237:(
16235:θ
16231:n
16229:(
16227:f
16223:n
16221:(
16219:g
16217:(
16215:θ
16135:.
16004:p
16002:o
15997:p
15995:O
15933:,
15930:)
15927:g
15924:(
15921:O
15918:=
15915:f
15907:g
15901:f
15878:O
15673:;
15670:)
15667:g
15664:(
15661:o
15658:=
15655:f
15647:g
15641:f
15621:)
15618:g
15615:(
15612:O
15609:=
15606:f
15598:g
15592:f
15579:O
15562:)
15559:x
15556:(
15553:g
15547:)
15544:x
15541:(
15538:f
15518:)
15515:)
15512:x
15509:(
15506:g
15503:(
15497:=
15494:)
15491:x
15488:(
15485:f
15458:0
15452:K
15432:g
15429:K
15423:f
15403:g
15388:f
15338:)
15335:)
15332:x
15329:(
15326:f
15323:(
15320:O
15317:=
15314:)
15311:x
15308:(
15305:g
15285:)
15282:)
15279:x
15276:(
15273:g
15270:(
15267:O
15264:=
15261:)
15258:x
15255:(
15252:f
15232:)
15229:x
15226:(
15223:g
15217:)
15214:x
15211:(
15208:f
15096:+
15069:L
15042:R
15027:o
14978:x
14976:(
14974:o
14969:x
14965:x
14963:2
14959:x
14955:x
14951:g
14947:f
14943:g
14939:f
14935:g
14931:f
14910:)
14907:g
14904:(
14901:o
14895:)
14892:g
14886:f
14883:(
14875:g
14869:f
14848:o
14844:g
14840:f
14827:o
14823:x
14819:x
14810:g
14806:g
14802:f
14787:.
14775:n
14737:,
14724:1
14720:)
14716:n
14701:(
14692:)
14688:n
14679:(
14676:)
14673:)
14670:1
14667:(
14664:o
14661:+
14658:c
14655:(
14651:e
14647:=
14644:]
14641:c
14638:,
14632:[
14627:n
14623:L
14607:L
14597:ε
14592:k
14588:n
14586:(
14584:o
14580:n
14567:O
14563:O
14559:k
14545:)
14542:1
14539:(
14530:O
14524:=
14521:n
14513:k
14488:)
14483:n
14479:2
14475:(
14466:O
14460:=
14455:n
14451:2
14447:n
14437:n
14433:)
14431:n
14429:(
14427:g
14420:n
14418:(
14416:g
14412:n
14410:(
14408:g
14406:(
14404:O
14400:n
14398:(
14396:f
14391:k
14387:)
14384:n
14378:n
14376:(
14374:g
14372:(
14370:O
14366:n
14364:(
14362:f
14353:n
14351:(
14349:g
14347:(
14345:Õ
14341:n
14339:(
14337:f
14328:Õ
14305:.
14302:)
14299:n
14296:(
14293:O
14290:+
14285:2
14281:n
14277:2
14274:=
14271:1
14268:+
14265:n
14262:3
14259:+
14254:2
14250:n
14246:2
14233:g
14231:(
14229:O
14212:.
14209:}
14204:0
14200:n
14193:n
14185:)
14182:n
14179:(
14176:g
14173:c
14167:)
14164:n
14161:(
14158:f
14152:0
14136:0
14132:n
14117:c
14106::
14103:f
14100:{
14097:=
14094:)
14091:g
14088:(
14085:O
14073:g
14071:(
14069:O
14052:.
14046:)
14037:n
14034:(
14030:)
14027:)
14024:n
14021:(
14018:g
14015:(
14012:O
14009:=
14006:)
14003:n
14000:(
13997:f
13984:f
13950:n
13946:n
13944:(
13942:T
13935:.
13933:n
13929:n
13927:(
13925:T
13920:n
13916:n
13914:(
13912:T
13907:n
13903:n
13901:(
13899:T
13889:)
13887:n
13883:n
13881:(
13879:T
13873:)
13871:n
13869:(
13867:O
13863:n
13861:(
13859:T
13853:)
13851:n
13849:(
13847:O
13843:n
13841:(
13839:T
13831:n
13827:n
13823:n
13821:(
13819:T
13811:O
13703:o
13683:O
13623:o
13583:O
13537:,
13515:,
13512:=
13509:,
13503:,
13497:,
13471:,
13448:,
13442:,
13436:,
13433:O
13430:,
13427:o
13407:n
13387:0
13381:)
13378:n
13375:(
13372:g
13347:0
13338:)
13335:n
13332:(
13329:g
13324:|
13320:)
13317:n
13314:(
13311:f
13307:|
13293:n
13267:)
13264:n
13261:(
13258:g
13254:k
13247:|
13243:)
13240:n
13237:(
13234:f
13230:|
13221:0
13217:n
13210:n
13201:0
13197:n
13189:0
13183:k
13168:g
13153:|
13149:f
13145:|
13120:)
13117:)
13114:n
13111:(
13108:g
13105:(
13099:=
13096:)
13093:n
13090:(
13087:f
13061:=
13055:)
13052:n
13049:(
13046:g
13041:)
13038:n
13035:(
13032:f
13018:n
12992:)
12989:n
12986:(
12983:g
12979:k
12973:)
12970:n
12967:(
12964:f
12956:0
12952:n
12945:n
12936:0
12932:n
12924:0
12918:k
12903:g
12899:f
12881:)
12878:)
12875:n
12872:(
12869:g
12866:(
12860:=
12857:)
12854:n
12851:(
12848:f
12825:0
12816:)
12813:n
12810:(
12807:g
12802:)
12799:n
12796:(
12793:f
12779:n
12753:)
12750:n
12747:(
12744:g
12740:k
12734:)
12731:n
12728:(
12725:f
12717:0
12713:n
12706:n
12697:0
12693:n
12685:0
12679:k
12664:g
12660:f
12642:)
12639:)
12636:n
12633:(
12630:g
12627:(
12621:=
12618:)
12615:n
12612:(
12609:f
12586:1
12583:=
12577:)
12574:n
12571:(
12568:g
12563:)
12560:n
12557:(
12554:f
12540:n
12507:|
12503:1
12494:)
12491:n
12488:(
12485:g
12480:)
12477:n
12474:(
12471:f
12464:|
12455:0
12451:n
12444:n
12435:0
12431:n
12423:0
12400:g
12396:f
12378:)
12375:n
12372:(
12369:g
12363:)
12360:n
12357:(
12354:f
12331:)
12328:)
12325:n
12322:(
12319:f
12316:(
12313:O
12310:=
12307:)
12304:n
12301:(
12298:g
12278:)
12275:)
12272:n
12269:(
12266:g
12263:(
12260:O
12257:=
12254:)
12251:n
12248:(
12245:f
12224:)
12221:n
12218:(
12215:g
12209:2
12205:k
12198:)
12195:n
12192:(
12189:f
12183:)
12180:n
12177:(
12174:g
12168:1
12164:k
12139:0
12135:n
12128:n
12119:0
12115:n
12107:0
12099:2
12095:k
12087:0
12079:1
12075:k
12047:1
12043:k
12020:2
12016:k
12005:g
12001:f
11982:)
11979:)
11976:n
11973:(
11970:g
11967:(
11961:=
11958:)
11955:n
11952:(
11949:f
11929:)
11926:n
11923:(
11920:g
11914:)
11911:n
11908:(
11905:f
11873:)
11870:n
11867:(
11864:g
11859:)
11856:n
11853:(
11850:f
11836:n
11810:)
11807:n
11804:(
11801:g
11797:k
11790:|
11786:)
11783:n
11780:(
11777:f
11773:|
11764:0
11760:n
11753:n
11744:0
11740:n
11732:0
11726:k
11701:k
11691:g
11676:|
11672:f
11668:|
11643:)
11640:)
11637:n
11634:(
11631:g
11628:(
11625:O
11622:=
11619:)
11616:n
11613:(
11610:f
11587:0
11584:=
11578:)
11575:n
11572:(
11569:g
11564:)
11561:n
11558:(
11555:f
11541:n
11515:)
11512:n
11509:(
11506:g
11502:k
11495:|
11491:)
11488:n
11485:(
11482:f
11478:|
11469:0
11465:n
11458:n
11449:0
11445:n
11437:0
11431:k
11406:k
11396:g
11392:f
11374:)
11371:)
11368:n
11365:(
11362:g
11359:(
11356:o
11353:=
11350:)
11347:n
11344:(
11341:f
11271:)
11268:)
11265:x
11262:(
11259:f
11256:(
11253:O
11250:=
11247:)
11244:x
11241:(
11238:g
11232:)
11229:)
11226:x
11223:(
11220:g
11217:(
11211:=
11208:)
11205:x
11202:(
11199:f
11144:.
11135:x
11115:)
11112:1
11109:(
11093:1
11090:+
11087:x
11055:;
11046:x
11026:)
11023:1
11020:(
11015:+
11007:=
11004:1
11001:+
10998:x
10966:,
10957:x
10937:)
10934:1
10931:(
10925:=
10922:1
10919:+
10916:x
10884:.
10875:x
10855:)
10852:1
10849:(
10836:=
10833:x
10801:,
10792:x
10772:)
10769:1
10766:(
10760:=
10757:x
10716:)
10713:)
10710:x
10707:(
10704:g
10701:(
10688:=
10685:)
10682:x
10679:(
10676:f
10656:)
10653:)
10650:x
10647:(
10644:g
10641:(
10636:+
10628:=
10625:)
10622:x
10619:(
10616:f
10596:)
10593:)
10590:x
10587:(
10584:g
10581:(
10568:=
10565:)
10562:x
10559:(
10556:f
10526:,
10521:+
10513:,
10458:L
10431:+
10404:R
10363:)
10360:x
10357:(
10354:g
10349:)
10346:x
10343:(
10340:f
10326:x
10295:x
10275:)
10272:)
10269:x
10266:(
10263:g
10260:(
10255:L
10247:=
10244:)
10241:x
10238:(
10235:f
10223:;
10211:0
10202:)
10199:x
10196:(
10193:g
10188:)
10185:x
10182:(
10179:f
10165:x
10134:x
10114:)
10111:)
10108:x
10105:(
10102:g
10099:(
10094:R
10086:=
10083:)
10080:x
10077:(
10074:f
10049:L
10022:R
9994:)
9991:)
9988:x
9985:(
9982:g
9979:(
9976:o
9973:=
9970:)
9967:x
9964:(
9961:f
9941:)
9938:)
9935:x
9932:(
9929:g
9926:(
9920:=
9917:)
9914:x
9911:(
9908:f
9878:|
9872:)
9869:x
9866:(
9863:g
9858:)
9855:x
9852:(
9849:f
9843:|
9831:x
9800:x
9780:)
9777:)
9774:x
9771:(
9768:g
9765:(
9759:=
9756:)
9753:x
9750:(
9747:f
9687:g
9683:a
9679:g
9675:f
9628:a
9622:,
9610:a
9604:x
9584:)
9581:)
9578:x
9575:(
9572:g
9569:(
9563:=
9560:)
9557:x
9554:(
9551:f
9500:.
9497:)
9494:h
9491:(
9488:o
9485:=
9482:f
9462:)
9459:h
9456:(
9453:o
9450:=
9447:g
9427:)
9424:g
9421:(
9418:o
9415:=
9412:f
9381:.
9378:)
9375:G
9369:F
9366:(
9363:o
9360:=
9357:g
9351:f
9331:)
9328:G
9325:(
9322:o
9319:=
9316:g
9296:)
9293:F
9290:(
9287:o
9284:=
9281:f
9258:)
9255:g
9252:(
9249:o
9246:=
9243:f
9237:c
9217:)
9214:g
9211:(
9208:o
9205:=
9202:f
9192:c
9170:0
9167:=
9161:)
9158:x
9155:(
9152:g
9147:)
9144:x
9141:(
9138:f
9124:x
9096:)
9093:)
9090:x
9087:(
9084:g
9081:(
9078:o
9075:=
9072:)
9069:x
9066:(
9063:f
9053:x
9051:(
9049:g
9043:.
9031:)
9026:2
9022:x
9018:(
9015:o
9007:2
9003:x
8999:2
8978:)
8973:2
8969:x
8965:(
8962:O
8959:=
8954:2
8950:x
8946:2
8936:g
8932:g
8928:g
8924:g
8915:ε
8906:M
8881:.
8872:x
8852:,
8849:)
8846:1
8843:(
8840:o
8837:=
8834:x
8830:/
8826:1
8806:)
8801:2
8797:x
8793:(
8790:o
8787:=
8784:x
8781:2
8755:.
8750:0
8746:x
8739:x
8730:)
8727:x
8724:(
8721:g
8711:|
8707:)
8704:x
8701:(
8698:f
8694:|
8668:0
8664:x
8653:ε
8630:x
8621:)
8618:)
8615:x
8612:(
8609:g
8606:(
8603:o
8600:=
8597:)
8594:x
8591:(
8588:f
8575:x
8571:x
8569:(
8567:g
8559:g
8555:f
8551:)
8549:x
8547:(
8545:g
8540:)
8538:x
8536:(
8534:f
8529:)
8527:x
8525:(
8523:f
8518:)
8516:x
8514:(
8512:g
8507:)
8505:x
8503:(
8501:g
8496:)
8494:x
8492:(
8490:f
8483:x
8481:(
8479:g
8477:(
8475:o
8470:)
8468:x
8466:(
8464:f
8458:.
8444:O
8432:,
8420:0
8393:)
8385:+
8382:c
8378:n
8374:(
8371:O
8351:)
8346:k
8342:)
8338:n
8329:(
8324:c
8320:n
8316:(
8313:O
8304:,
8292:0
8286:c
8265:0
8259:k
8238:)
8233:n
8229:n
8225:(
8221:O
8218:=
8215:)
8212:n
8209:(
8206:f
8186:)
8183:!
8180:n
8177:(
8174:O
8171:=
8168:)
8165:n
8162:(
8159:f
8107:)
8104:!
8101:n
8098:(
8095:O
8053:1
8047:c
8027:)
8022:n
8018:c
8014:(
8011:O
7969:1
7957:0
7927:1
7923:)
7919:n
7904:(
7895:)
7891:n
7882:(
7879:)
7876:)
7873:1
7870:(
7867:o
7864:+
7861:c
7858:(
7854:e
7850:=
7847:]
7844:c
7841:,
7835:[
7830:n
7826:L
7775:)
7770:c
7766:n
7762:(
7759:O
7718:n
7697:)
7692:2
7688:n
7684:(
7681:O
7651:"
7649:n
7645:n
7626:)
7623:!
7620:n
7611:(
7608:O
7605:=
7602:)
7599:n
7590:n
7587:(
7584:O
7554:1
7548:n
7538:,
7535:)
7532:n
7523:(
7507:+
7504:1
7497:1
7491:n
7481:,
7478:0
7472:{
7467:=
7464:)
7461:n
7458:(
7425:n
7419:n
7404:)
7401:n
7385:n
7382:(
7379:O
7362:n
7341:)
7338:n
7335:(
7332:O
7300:1
7294:c
7288:0
7268:)
7263:c
7259:n
7255:(
7252:O
7217:1
7211:c
7191:)
7186:c
7182:)
7178:n
7169:(
7166:(
7163:O
7121:)
7118:n
7109:(
7106:O
7073:)
7070:n
7055:(
7052:O
7018:)
7015:)
7012:n
7009:(
7003:(
7000:O
6971:n
6967:)
6963:1
6957:(
6930:)
6927:1
6924:(
6921:O
6895:n
6891:c
6861:O
6835:)
6830:2
6826:n
6822:(
6819:O
6800:n
6796:e
6794:(
6792:O
6787:)
6785:e
6783:(
6781:O
6777:n
6768:n
6766:(
6764:g
6760:n
6756:e
6754:(
6752:O
6748:n
6746:(
6744:g
6740:O
6736:n
6734:(
6732:f
6728:O
6720:O
6698:.
6695:)
6690:n
6686:e
6682:(
6679:O
6676:=
6667:)
6664:1
6661:(
6658:O
6654:n
6646:,
6643:)
6638:2
6634:/
6630:5
6626:n
6622:(
6619:O
6616:+
6611:3
6607:n
6603:=
6594:2
6590:)
6586:)
6583:n
6574:(
6571:O
6568:+
6565:n
6562:(
6556:)
6553:)
6548:2
6544:/
6540:1
6536:n
6532:(
6529:O
6526:+
6523:n
6520:(
6513:,
6510:)
6507:n
6504:(
6501:O
6498:+
6493:2
6489:n
6485:=
6476:2
6472:)
6468:1
6465:+
6462:n
6459:(
6429:n
6419:O
6407:n
6405:(
6403:O
6397:n
6395:2
6391:)
6389:n
6387:(
6385:O
6381:n
6377:n
6375:(
6373:T
6366:n
6362:n
6356:n
6354:(
6352:O
6348:n
6346:(
6344:T
6340:n
6314:.
6311:)
6308:)
6305:x
6302:(
6299:f
6296:(
6293:O
6290:=
6287:)
6284:x
6281:(
6278:h
6272:)
6269:x
6266:(
6263:g
6237:)
6234:)
6231:x
6228:(
6225:f
6222:(
6219:O
6216:+
6213:)
6210:x
6207:(
6204:h
6201:=
6198:)
6195:x
6192:(
6189:g
6176:x
6174:(
6172:f
6168:x
6166:(
6164:h
6158:x
6156:(
6154:f
6152:(
6150:O
6146:x
6144:(
6142:h
6129:C
6125:)
6123:x
6121:(
6115:)
6113:x
6111:(
6109:h
6102:x
6100:(
6098:h
6094:x
6092:(
6090:g
6088:(
6086:O
6082:x
6080:(
6078:g
6076:(
6074:O
6070:x
6068:(
6066:f
6062:x
6060:(
6058:g
6056:(
6054:O
6047:x
6045:(
6043:f
6037:x
6035:(
6033:g
6031:(
6029:O
6025:x
6023:(
6021:f
6009:)
6007:n
6005:(
6003:O
5999:n
5994:)
5992:n
5990:(
5988:O
5984:n
5978:n
5974:n
5965:)
5963:x
5961:(
5959:O
5955:x
5953:(
5951:O
5946:)
5944:x
5942:(
5940:O
5936:x
5934:(
5932:O
5917:x
5915:(
5913:g
5911:(
5909:O
5905:x
5903:(
5901:f
5896:x
5894:(
5892:g
5890:(
5888:O
5884:x
5882:(
5880:f
5848:2
5844:)
5837:,
5834:0
5831:[
5809:2
5805:)
5798:,
5795:1
5792:[
5772:g
5752:f
5732:)
5729:)
5726:m
5723:,
5720:n
5717:(
5714:g
5711:(
5708:O
5705:=
5702:)
5699:m
5696:,
5693:n
5690:(
5687:f
5667:n
5664:=
5661:)
5658:m
5655:,
5652:n
5649:(
5646:g
5626:1
5623:=
5620:)
5617:m
5614:,
5611:n
5608:(
5605:f
5578:n
5571:M
5564:C
5557:m
5525:n
5516:)
5511:m
5507:n
5503:(
5500:O
5497:=
5494:)
5491:m
5488:,
5485:n
5482:(
5479:f
5470:m
5440:m
5433:n
5426:M
5419:C
5387:m
5384:,
5381:n
5372:)
5367:m
5363:n
5359:(
5356:O
5353:=
5350:)
5347:m
5344:,
5341:n
5338:(
5335:f
5311:x
5290:M
5284:n
5264:M
5258:m
5234:|
5230:m
5227:+
5224:n
5220:|
5216:C
5209:|
5205:)
5200:3
5196:m
5192:+
5187:2
5183:n
5179:(
5173:)
5170:m
5167:,
5164:n
5161:(
5158:f
5154:|
5140:M
5136:C
5113:m
5110:,
5107:n
5098:)
5095:m
5092:+
5089:n
5086:(
5083:O
5080:+
5075:3
5071:m
5067:+
5062:2
5058:n
5054:=
5051:)
5048:m
5045:,
5042:n
5039:(
5036:f
4998:x
4974:M
4957:x
4933:i
4913:M
4905:i
4901:x
4880:.
4877:i
4857:M
4849:i
4845:x
4823:x
4801:|
4797:)
4793:x
4789:(
4786:g
4782:|
4778:C
4771:|
4767:)
4763:x
4759:(
4756:f
4752:|
4731:0
4725:C
4705:M
4675:x
4665:)
4662:)
4658:x
4654:(
4651:g
4648:(
4645:O
4637:)
4633:x
4629:(
4626:f
4601:n
4596:R
4574:g
4554:f
4544:O
4540:O
4519:.
4516:)
4513:g
4510:(
4507:O
4504:=
4501:f
4495:k
4475:)
4472:g
4469:(
4466:O
4463:=
4460:f
4440:)
4437:g
4434:(
4431:O
4428:=
4425:)
4422:g
4415:|
4411:k
4407:|
4403:(
4400:O
4390:k
4364:)
4361:g
4358:(
4355:O
4335:)
4332:g
4329:(
4326:O
4318:2
4314:f
4310:+
4305:1
4301:f
4280:)
4277:g
4274:(
4271:O
4268:=
4263:2
4259:f
4238:)
4235:g
4232:(
4229:O
4226:=
4221:1
4217:f
4196:)
4193:)
4188:2
4184:g
4180:,
4175:1
4171:g
4167:(
4161:(
4158:O
4155:=
4150:2
4146:f
4142:+
4137:1
4133:f
4112:)
4107:2
4103:g
4099:(
4096:O
4093:=
4088:2
4084:f
4063:)
4058:1
4054:g
4050:(
4047:O
4044:=
4039:1
4035:f
4006:)
4003:g
4000:f
3997:(
3994:O
3991:=
3988:)
3985:g
3982:(
3979:O
3973:f
3952:)
3947:2
3943:g
3937:1
3933:g
3929:(
3926:O
3923:=
3918:2
3914:f
3908:1
3904:f
3897:)
3892:2
3888:g
3884:(
3881:O
3878:=
3873:2
3869:f
3860:)
3855:1
3851:g
3847:(
3844:O
3841:=
3836:1
3832:f
3813:)
3811:x
3807:O
3803:n
3798:x
3794:)
3792:x
3788:O
3783:x
3775:n
3771:)
3769:n
3767:(
3765:O
3760:2
3746:n
3742:2
3738:)
3736:n
3732:n
3729:c
3723:c
3717:n
3714:c
3703:n
3698:n
3689:3
3685:2
3680:n
3676:c
3672:n
3664:n
3660:O
3655:)
3653:n
3649:O
3644:n
3636:n
3622:c
3613:c
3608:n
3603:c
3599:)
3597:c
3595:(
3593:O
3588:)
3586:n
3584:(
3582:O
3569:n
3565:n
3548:.
3539:n
3530:)
3525:3
3521:n
3517:(
3514:O
3511:=
3506:3
3502:n
3498:2
3495:+
3490:2
3486:n
3482:3
3479:+
3474:4
3470:)
3466:n
3457:(
3454:5
3451:+
3448:n
3439:9
3436:=
3433:)
3430:n
3427:(
3424:f
3411:)
3409:n
3407:(
3405:f
3399:f
3386:x
3382:x
3378:x
3374:x
3370:e
3366:x
3364:(
3362:O
3341:0
3335:x
3325:)
3320:2
3316:x
3312:(
3309:O
3306:+
3303:x
3300:+
3297:1
3294:=
3284:0
3278:x
3268:)
3263:3
3259:x
3255:(
3252:O
3249:+
3244:2
3239:2
3235:x
3229:+
3226:x
3223:+
3220:1
3217:=
3207:x
3194:+
3188:!
3185:4
3179:4
3175:x
3169:+
3163:!
3160:3
3154:3
3150:x
3144:+
3138:!
3135:2
3129:2
3125:x
3119:+
3116:x
3113:+
3110:1
3107:=
3098:x
3094:e
3076:x
3047:=
3042:n
3023:)
3018:2
3014:n
3010:(
3007:O
3001:)
2998:n
2995:(
2992:T
2966:)
2961:2
2957:n
2953:(
2950:O
2947:=
2944:)
2941:n
2938:(
2935:T
2920:U
2916:T
2904:n
2899:n
2895:n
2893:(
2891:U
2885:n
2881:n
2879:(
2877:T
2871:n
2865:n
2851:n
2849:2
2844:n
2842:4
2836:n
2827:n
2822:n
2816:n
2812:n
2808:n
2806:(
2804:T
2799:n
2787:n
2783:N
2745:O
2740:)
2738:x
2736:(
2734:g
2679:.
2674:4
2670:x
2659:|
2655:5
2652:+
2647:3
2643:x
2639:2
2631:4
2627:x
2623:6
2619:|
2592:4
2588:x
2581:=
2569:4
2565:x
2561:5
2558:+
2553:4
2549:x
2545:2
2542:+
2537:4
2533:x
2529:6
2516:5
2513:+
2509:|
2503:3
2499:x
2495:2
2491:|
2487:+
2482:4
2478:x
2474:6
2463:|
2459:5
2456:+
2451:3
2447:x
2443:2
2435:4
2431:x
2427:6
2423:|
2407:0
2404:x
2400:x
2393:M
2386:0
2383:x
2377:0
2374:x
2370:x
2365:M
2360:0
2357:x
2340:4
2336:x
2332:M
2325:|
2321:)
2318:x
2315:(
2312:f
2308:|
2297:)
2295:x
2293:(
2291:O
2287:x
2285:(
2283:f
2273:x
2269:x
2267:(
2265:g
2258:x
2254:x
2250:x
2248:(
2246:f
2241:)
2239:x
2237:(
2235:O
2231:x
2229:(
2227:f
2221:x
2216:)
2214:x
2212:(
2210:f
2204:x
2198:x
2192:x
2187:6
2182:x
2180:6
2175:x
2173:6
2169:x
2165:5
2160:x
2153:x
2151:6
2147:x
2142:O
2135:x
2131:x
2127:x
2125:(
2123:f
2114:x
2110:)
2108:x
2106:(
2104:f
2096:)
2094:x
2092:(
2090:f
2081:x
2076:O
2051:0
2047:n
2040:n
2020:)
2017:n
2014:(
2011:g
2008:M
2002:)
1999:n
1996:(
1993:f
1971:0
1967:n
1946:M
1924:)
1919:)
1916:x
1913:(
1910:g
1905:(
1900:O
1897:=
1894:)
1891:x
1888:(
1885:f
1861:g
1841:f
1811:a
1805:x
1775:a
1755:g
1735:f
1691:a
1668:.
1656:)
1653:x
1650:(
1647:g
1642:|
1638:)
1635:x
1632:(
1629:f
1625:|
1617:a
1611:x
1586:a
1580:x
1569:)
1564:)
1561:x
1558:(
1555:g
1550:(
1545:O
1542:=
1539:)
1536:x
1533:(
1530:f
1506:x
1486:)
1483:x
1480:(
1477:g
1457:.
1454:)
1451:x
1448:(
1445:g
1442:M
1435:|
1431:)
1428:x
1425:(
1422:f
1418:|
1408:,
1389:|
1385:a
1379:x
1375:|
1368:0
1347:x
1327:M
1287:a
1281:x
1270:)
1265:)
1262:x
1259:(
1256:g
1251:(
1246:O
1243:=
1240:)
1237:x
1234:(
1231:f
1211:0
1208:=
1205:a
1185:a
1165:f
1145:.
1140:)
1135:)
1132:x
1129:(
1126:g
1121:(
1116:O
1113:=
1110:)
1107:x
1104:(
1101:f
1081:x
1061:.
1056:0
1052:x
1045:x
1036:)
1033:x
1030:(
1027:g
1024:M
1017:|
1013:)
1010:x
1007:(
1004:f
1000:|
977:0
973:x
952:M
930:)
925:)
922:x
919:(
916:g
911:(
906:O
903:=
900:)
897:x
894:(
891:f
871:x
851:)
848:x
845:(
842:g
822:)
819:x
816:(
813:f
789:)
786:x
783:(
780:g
760:)
757:x
754:(
751:f
725:x
714:)
709:)
706:x
703:(
700:g
695:(
690:O
687:=
684:)
681:x
678:(
675:f
655:x
635:)
632:x
629:(
626:g
595:g
567:f
549:Θ
544:ω
540:o
453:O
439:e
432:t
425:v
327:.
313:0
309:x
302:x
280:)
277:x
274:(
271:g
266:M
258:)
255:x
252:(
249:f
241:0
221:5
218:=
213:0
209:x
186:0
182:x
161:1
158:=
155:M
135:0
129:M
103:x
81:)
78:)
75:x
72:(
69:g
66:(
61:O
58:=
53:)
50:x
47:(
44:f
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.