Big 0 oouuion • Wikipedia. the free encycloped ia
`
`Page I o f lJ
`
`.... q...- ...... -_.I* .... _, ..... ..
`
`Big 0 notation
`r .... "'-........... r--,.: ......
`"" ~ O-"_ d - .ibo:.Ik-.otbduJ>'""oI •
`t.~,,!b.
`............. _
`...r .. ~y . ...Ily .. _
`of .......... fun<1--. " ........... of.
`Iw@'II' r.o.;ly of"",",,,,,,, _
`.. alia! Loiod •• __ ... .
`B.( ............... u ""'., ... (In ... I~ I ........ tn<Il'oul
`I I.d"_~I'">l '" .'l'mp' .... -..ion. In rooIIfI'*' "''''''''c. "" 0
`""',,11On .. "'"'" '" da!i!.lfy Ilpili11hn>o by how Iky rn:pond (r,z .. ..
`1h<1I ~ ,,"'" .. """"""Sf*<" """",""'-.1 ~,<honp ..
`,~ .. '" I~ I ..... l}'''" ......bn ""'-Y. ,I " .....l '" ... on .. !C I,,",
`' """, _~I<d" "'~,k ~ tb< .. ympiOU< ...... ..
`"r",,,IOI"''''. >ole. of • ....amrucoJ fullCl",,1>y the ... 1.., . ..
`....... . Un . ,. """" r .... q
`.......... A ........ HIiIIpk ..
`_
`trl<ml ...... ~_
`
`.... .-01 ....... u......
`
`•
`
`•
`
`I
`
`I
`
`•
`
`-~
`II .. O_~f __ ~ ...... ....,..do
`laic> .. Ilmao J>.;t""" .. 1IIo . . __ tIo TIl< -r k
`"p' ..... ,d _ " ' ..... 0 ___ Tb< _0 nWld,,",,-
`doc: ..-_ nrI< oI. f....,...,. .. _
`~ct1<'d "' .. _
`oil,,",
`funct-. 1\ dn;mp"'" 01. r-....... !II I<mI> 01"" 0 ""'"'_
`....... 11y....,. ..... ·Kb .. """'" braid "" doc: .,.,.,111 nrI< of I'"
`fun,;:,_, """""""" '''1II "" 0 ~"'" ..., _ · .... 1 ",1aIod
`" "I"I~""' . ... "" tb< .}'mIJOh ... Q _, ond a .... <ba,,,", <>I/K"r k ......
`un."" ........ ")'''I~Ill'''' ¥' ..... -ilt . WOt:s
`"'11 0 ...... _
`.. ,I.., ...ru • .....y0lbcr ( .. lob ......... 'ide ,,",uLor ."."""""-
`
`f----,< oIS.0 _~ -..1 • 0(01..,)- - . ....... ~ ~0 4 . ..
`~ - L)_ .. L . ..... ' )_ .... _.) ~ $1 ._,..~ ,. ...
`
`Contents
`I "...-""r .......
`
`' l~~ ,-• ll infinolcbfmp"'''''
`.-.. ~
`
`• J .2 tnf..,l<>unII_j1l'lf*!ll<>
`
`• • 2 Sum
`• • ..1 Muillphc_ by. =, .. '"
`3 ~h"""'" , . .,-w, .. ...
`6 M ...... IIf ....... "'"
`6.1 t;qu..ls_
`' .2 00'"" .,.,."..., op<nI<>n
`• 6.l_l l .........
`O llooc _ _ 01_
`U Muhipk .....
`7 0Nm 01.",...... f_
`• Rdoa<d.s)~_ ....
`• 11 .... ' - '_
`.. l li'.o.n.p .......
`W_2 Ilk II..-d)'-I~II ..... -ood do,,-L_
`. _2 1 SuttfJIo ~
`•
`• 3.l.l Thr t:.a.1It deft",L"'"
`8..1h.mlyof llad"'.",I .......... _
`• ~ U"" ,n wonpuI<.T ""I<f>.:C
`
`•
`
`NETWORK-I EX HIBIT 2009
`Google Inc. v. Network-l Tedmologies, Inc.
`I PR20 15-00345
`
`fil(':/IIC:JU~lalA DatalLocalfTtm W2EIM09.hlm
`
`911512015
`
`1)llge I of 13
`
`

`
`Big 0 notation - Wikipedia. the free encyclopedia
`
`Pase 2 of IJ
`
`• S..'i E>. .. """"" 10 Ihc: Ibdll"."D-I.MJdau 00l.iI""""
`9 <i<a<ro1il.alWOS ond rdawJ ~>
`10 1I1>lOlJ' ( 1Iao<hlll" ..... I.MJda .. II.rdy. and Vi~ oow.,...)
`11_ .... '
`12 Rcfcrcn<cs and N.-.
`13 rlKtbn rndi"l!
`14 1",...,..1 !in~.
`
`Formal definition
`
`Lctfand If I>< I",,, function. def ..... 011 """" ......... "f,b< ",,,I ........... 0,-., ,mlcs
`
`if.,loI.! only ,ftboR i .. p<»i1"'" 00DSUnI M such ..... for on ",rr.ci .. IlIy Lu,. ,..J"", of r , lh< abool",~ ,....., ofJlr) ; ... """'" M
`n)ullipli.-d by >lie ......,1"", ......, " f ...,;r). 1ho1 ;"'hl _ ~,,» ,f - ' ""'y ,fib ..... =>1> a _iii". ~ .....,.". ,If >noJ a ~ ...... >b<, ..-.
`...,h 1ha1
`
`In ",a"y """"",Is. Ihc: 0"""""""" ,hal we.,.., "' .......... n , .... $"' ...... .-ale os ..... , ... ,...., x goes,,, "("'11]/ .. 1<11 """,N. and """
`'HIl"" mon: ~y thalftr) - G\g(z))_
`
`I {'I) = 0 (9(%» lIS r --f a
`
`if and O!Ily if~ ox ... .-,'"'' """""'" oJ 00.1 M....,b 1hal
`I/ (z)l:5 Mlg(zll ror Iz - (II < 6.
`
`I (z ) = O(g( z )) lIS r --f a
`
`Add,,,,,, .. ,Iy . .... OOl.iI.;o" ~r));' ols<, used 10 _ , .... SCI oron """"ions Ar) tbaI ... ,,1Y 11K: ",bI_A rJ"<ll:.!l(r»). .. ,"'. <OS< " ..
`'''''e
`
`I (r) E O(9(r»
`
`Exa mple
`
`In 'ypint ~, I.bo: fonnal dcIi""1OO of 0 __ .. "'" """"dm:c1ty; .. 1lI<1, 1I>c0 __ foro f ..... _ f .. dcr"'odby ....
`rollo"·,,,, ~,r"",I"'" odco:
`• IfJlx) .. 0 • ..,,, of ""'~ ,""""- tho """ .ntltlhc: wI!<'" _,. ""e i. l "",. - ' all oIJ."'''''>IIlI«l
`• If..(r) .. 0 prn>/u<t 0( ... 'tfllI (""'on. .. y C'."' .... ",'it"""" 1m W: pcoW:;' ..... do _ dcp<-nd OIl xl"'" "",,,,cd
`
`For en ....... Ict..(r) _ 6<' - b' • 5. and ""I'I'<"C "' .. ",,>I> "' Slmpllly ibis fWlClioro. ... "" 0 001311"". '" dc;c:rib< il< p""lh .-- os J(
`"""machos ...r .. ity. "Ih;" firn<t"", .. ,t.;, ...." of~ ..,""., ........ -2>"'. md S. or1.llo:o< tin< , ....... .... OIl< ""tit ,b< hig/>nt p""lh ",' e
`" lire """ ",-nil "'" 1arg<'1 c:<pOOC1I1 ... fune""" <M~. """"'Iy ...... • ~ one may IIJ'I'IY "'" """""" rule: v' IS. pro<b:1 <M 6 md~' ,n
`
`Page 2 of 13
`fileJlfC:JUst:T"SlklaiA DmaiLocalfTent W2EIM09.hlm
`
`91151201 5
`
`

`
`Big 0 notation - Wikipedia. the free encyclopedia
`
`Pase 3 of 13
`
`which th< r .... fador 00.. ... d<p<nd on x. 0mIIUJq!; Ill" fac''''' ~ .. ,lot .inoplirO<d lOOn x'. , """- .... oay """JI~J .. a "bog..,to- of
`(x'). MOllo.m ... c.lly. ".~ """ ""''''.A .• ) " (\t') On< may cooflml ill .. <"kula,,,,,, ""1Ii! "'" ro ... ",) dor""l_ 10'/1;<) " c..' - 2<' • 5
`and S<~) " ~' Applying ltoo ("""",I ""fin""", from """'·e. ,too _""""" """/I~) " 0(.<') .. """,,,,,k-nloo ItS "po.n""".
`l/(x)l.'5 M )g(.c)1
`
`16x~ - 2.? + 51 .'5 6x' + 12",'1 + 5
`< 6x' + 2.r' + Sx'
`= 13r'
`
`16,r' - 2,r3 + 51:5 13,r' .
`
`Usage
`
`II" 0 __ ..... laos IWo ma .. __ of opplio<a'''''', In malOCmalK:O. n .. ron.nonly ..<all<> d<>r,ibe: ....... obdy. fin;" """'"
`lJ1!l"''''''''IcS. !i''rn func' ..... npo< .. tly in th<.,..., of. ,,,,,",,,led l'oyk:.- """'" .,.. a.ympoOl!!< cx~ In <:OIIIf'Jl<' >cIcD<'c:. " is
`.... ful ,n lI,e _} .... ofa~ In boIh oppI_ ....... ,be: funotOl1lg(;t) ~ .. "hon the 0(" ., "I)."ally c".,.." 10 be: IS . "npl •
`• s """,bIe, om'lIong """ ..... ' &.;ton and ""'-.,. ord<f ",,,.,.. ll><'re..., "''-0 fomuJly < ..... 10." nofi<oabIy doff"""", . .... ~ .. ofdu.
`.... ...-.toc:
`nOOolion: i.r .... ", IS)'IOP''''''''"'''' inlin"~'unal .. ~"'~ Th .. di"uot1;"'" .. only .. """,~I"'" and ..... r->n,,,plo. _
`r""",,1 <li:fin,""" fOf IhI: "big 0" .. Ihc .. me: lOr 00Ih ~ ooly ",110 <lifTm-nllimns lOr Ib: f"IIC",", >qoIJl1mI.
`
`Infinite asymptotic5
`
`lJ'i 0 ___ is •• <ful "hm _lylO"l! al$Onllms KII efliol<l1O)'. r .. <"""1"0. II .. IUD< (00' " .. nOnlb:r of SlOps) ill.W:s 1O«JmpI<-\< •
`:'It • 2. "" ~ P""'-' lo'l!~. Ihe ": I<nD .. -,il """'" "' ......... "' . Ii<> ,1000 011 <><bo"""",
`"""'"-." .. >1' ..... ~ mlgh' be found ... lot 1(n)" . ,,: -
`(Of ~ " ...... w • 500. l/oc o..-m ."' i. IllOO .m... .. lo'l!< .., .... 2<0 ....... I&""""I! 010< ","", .. ..,..ad "-' ..
`.... be ""II"""ed
`ncgl'SOI>k dr.", "" II>< cxP<"""""'s , .. hI< ro. _
`JUI"I"'S ~unhct. obc: """lfocien" I><:cotnc i",,\O:>_,( .... """"""" lO"y «h<...(cid:173)
`
`(If11...- of "'fIRWOI'. '''''h '" OIl t:lprc><oon oonuo'""'l! • kfln n' ... ' E,,,,, 'f 7l.,,) - t.OOO.ooo..'. if l,l., -,,', II>< lOll .... ·~I.ho'3)"
`<xcoed .... t<onn..- ",",c "!_" ~ ""'n 1.000.000 m 1.000.000) - 1.000,000'- {A:1.000.000»), AoldibOdaIly. ,he: oaaoba- 0( ""l"
`dct><-nd:; IJII ,boo doIo;l. of Ibe machinc model IJII .. bleh "'" a1l"""ihm IU~ bul dilJemlllypes "fmad"""" I)pically 'lIr)' by IJIIIy I
`<:<10"""', f.......- m obc: nwnbc.- of .. "", occlod "' CU<'UI< an alB-m.. So !he hog O.ubooo ""plum " .... '''m:nns' .. " ".-no< alba
`
`and .. y """ "'" oIj!:Ori,hm """ <>ftkrofn-' hmo "" .. "lIu;,y. NOIe "'"' """ .. not n"""" ... ~ ." ....... "," '0 ,IS oonnaI
`... "I>o",,,,,onoI ....,... I>uI ""M ....... «.>lIoquoal "IS-. '" ,I>< , ... .-on.! ""1I"0SSI0I1 OS "",,,,,,colly ",conte (s« lboo "Equa" ..,.," do-;.;:,."joo
`bel"w, ... -hik !he fust ; ..... okm;l by """'" ..... _of DOIaIiooo.l'I
`
`Infinit esi mal Isp n ptolK-s
`II" 0<.:01100 be u>ctI,o--.ibe tho: <m>r I<rm '" ... 0JlP"l'."""""' ... . .... , _ fuocIion. 11><..- .. gruf .... "' ....... ..-.
`... ~"" ....... i<-1Ily. an.! 'hm ""' 1<asI_.'~nir...-- ........ '" ... ~ .... " "!Ik bog 0 I<rm_ Con»<lo-. b- ~Io. l/oc """"""",,.1
`.....-in .nd 110.-0 CXj>I<'>,ions ofi' """ "" ",,'id .. -hrn X i, """II
`
`Page 3 of \3
`fileJlfC:JUst:T"SlklaiA DalaiLocalfTenJ W2 EIM09.htm
`
`91151201 5
`
`

`
`Big 0 notation - Wikipedia. the free encyclopedia
`
`Pase 4 o f IJ
`
`~2 r
`~4
`c."=1+T.+ 2!+3!+ 4!+
`.'
`- 1+~+2+0(r)
`= I +~+O (r)
`
`for I'll .c
`
`"" ~ --+ O.
`
`... ~--+O.
`
`The ~ OPI'''''''''' (Iho ....... ,110 O(x'») ".,...... \he abso.'IOk-' ...... oflh. mor tf - (I +;r -+- rf2) "sm:tlk-< 11>>11 ....... ""'blnnl
`tin ... ~I .. '"",,;r is 01_ """"" 10 o.
`
`Properties
`
`lIS " --+ 00.
`In )l>rti<.-ubr. ira f.....,,;"" I1IIIY "" bound .. :d by • poI)""",,;,1 in ~. ""'" as ~ londs 10 "'foonJ·, """ ,,"y di .. oprd "'"'~ I<nn< " f ill<
`poIynonuaL ADoIbrt th,o, 10 0<IIr<: .. Ih<: setS Q:,.') ... .1 Q:<") Ire ''CfY different If c ,,~er iIl>ll OlIO. Ibm lho .. 11 .. P""" much
`("'ler. A funotion ,1Ia1 gro"~ fa;on IMO ~. (or til)' ~ IS ""lied ",~_;"I. One 'h'" p"".' ,"""" ....... 1y lllan any .,.....-.. 1
`IUnctioD of 11M: I'orm c" is ""tied ~IUJ AIo oIpilbm <an =l"in: lime Ibal .. bodo ~"1pOI~ ond :iUbcxpoDrnIiot
`••• .."ples oflh" "",IWe \he f ....... 1;00\\'0 olgo!llhaw rOf tnl<!!U f""OOtIIaM'" on<! Ibt /\Inc,,,,,, n"'·
`We may """'" any I""'~"'" of ~ .... "'" oflh< ....... 1Im<. 'Ik "'" 0(.,. w) i< <''''''1)' ,II< ....... ., 01: ... ..,) Thc Iopnllm< differ '"'I)'
`by 0 ~ r..-"" (.inc.: ... ,(') - c log ~) and IlIu< Ihc bi~ 0 "",",,,,,, """"" IboI. Simolorly. 1"1\< .. ,.., diffnrn' ~ ba>C5 ar.
`«JU i ... knL 0.. Ihc: ",her "'-l npanmliol, ",Ib diffrn:nt Ix>sn .... _ oflhc: >am< ordcT. F ... ex"",*," :r ond J" ... no! oflhc: .. Ill<
`0 ... ,,:.,
`
`Cl\anglng _ may (10' may ..,. :tlT«1 """ lII'detofdl< 11'<I.li!"" oI~ C ..... 1P"8 ""'" .. <'«Ui, .. 1<rII1n mulhl'l).'tng .... ~"
`, ... ,.bIe by. """"""I ,,'hem,.,. ""1'1"'""' .•. ". _10. if on oIJ1l1llhm run. ,n !he order 0/" w' .... -pi"",.,. ~ by "" ,,..,... Ihe olgonthm
`....,... tho ""'_ .r. lb<. <an be "TUt"" .. r'.r - 0(.1). If. """."'"e\' .... oIgontlun
`""'" '" Ihc: ordcT of ~.r. and .... bt, 0 OOIlIt_
`runs in Ihc: ordcT 01"2", rq>b<:mF. ,,"'h en ~".c; ~ _ (2')'. Thi ... _ Olwvalrnt '" :r ID 1!<""'f"1. ~"" ' ·anabl .... ""'y aI>o a!l<'ct
`.... onkt ofllM: ...-sulti nS a1l1lfltllal. 1'<>< .xamplo. ,f ... olgorithnl'. run"'" i. O(~) ",beD m<a>1Ired ID I<nm af llN: nombet ~.,. digil. of
`an inpul """""'" :<. 1b<.'It ,ts "'" ..... ,. O(lOJ~) WI """ mea.1Ired OS a rl1ll<'11Ot1 of tho Input .... nb<.1 k .self. 1«<""", n - 0(1ot .. ).
`
`P rod UCI
`
`I. = O(g,) lind h '" O(Jhl - "h E O(gIJh)
`I· O{g) = DUg)
`
`S"m
`" = O (Yl) 11".1 12 '" 0 (1h) .... II + 12 = 0 (1911 + l!hl)
`1lIis implits" := 0 (1') lIud h = O(g) aj. II + h € O (g} ,,1tM:~ moan. thai 0(1') io a """'·"" ......
`If/_g .... p<>!ih' .... fl1ll<'1lOD>,1 + O(g) :::::: OU + g)
`
`Multiplicalion by.ll ronSllin t
`
`I. .. k be a roo>I ..... 110m:
`0(1;1') = O(g)Ifk .. "" .. , .. ,ro.
`IE 0 (9) '* kl = 0 (9)·
`Multiple "ariables
`
`Page 4 of J3
`file JIfC:JUseT'SlklaiA DataiLocalfTem W2 EIM09.hlm
`
`91151201 5
`
`

`
`Big 0 notation - Wikipedia. the free encyclopedia
`
`Pase 5 o f IJ
`
`f (i') is O(g(:1) as z -+ 00
`
`3.\1 3C> 0 !lum Ilult for 1111 Z ...-ith.r, ~ :II for some i .I/ (])]:5 CIg(1)I.
`F.qui,"IetlIy. Ibe l;<JDdill"n ",,".7, ~ M for $lHJIO ; can be n;-pIao:od "ilb th. oondiriDn thal lI:i'J1 ~ M . ...... lIlJl ~ IlIo
`Chcl>r>f>rv .. i>tan<~. I'or eu>~. Ibt ... t ........
`f (n.m) = fl2 + ml +0(,,+ m ) as II. fit -+ oc
`
`VII( n.m)U ~ M : 19( n.m)1 :5 C (n + m).
`
`f( n. m) = ,,1 + fIl l + gen . m).
`NOlo tllaC Il100 d<f!JtJlion .11ofo·ull oflhc ~ af z l<> u><rca;<" 10 .. fmily. In partI<IIIm". 11>1: >W<nIO:IlI
`f(n.m) = 0(,,"') M n, m -+ oc
`(i .• .• 3C 3.11 V" V ... .. ) IS quol~ d,ITm-nc """
`Vm: / (n. m) .. O(n"') 8.5 fl -+ OC
`(i.~ .. V'" 3C' 3,u 'r/ .. .. ).
`
`Thi' ,,"'" IlIo only lP'fI<",hnl"", ofbig 0 10 ....... , ... ,'" rIO"''''''''. __ In PlOCI~ ...., to """'" ~ in the ~ af
`dcfinin.....'"
`
`Matten Or notation
`Eq UJ ls sign
`
`The , .. 1< ...... "ft~) " ~,,»)" ao <l<:ti ... " abo\-.: IS uswlly ""nllm _ A~) - ~~)~ s.:.n.. «>mKlcr IhlS'" be: an ...... af _loon. .......
`the use aflhc <qUaL< .ogn «JUId be: "".I.>dt"ll a. ~ ~< • • )-..netry lhat tho> SlaIemm1 dots "'" ha\-.: lis de lJlU!)t1 oays. 0(..) - 0
`(r) i. true bill O(r) _ O(x) .. _.I~ Knuth <lescribo. "",h >1'''''''''''''' _ "one-" .. y oquoli'''''"' ,me., if"'" ....,. coold hc ,,",=std. '''"0
`cool<! doducc n.I"",Ioo, Ibll'''' lit. w - w' from Ibt idrft.itie> w - O(.i) and .r - O(.i~ ~ F", th">< ,.,...,.... it would hc '""'" PRC"" to
`QO(' "" ~ lJId "'lil~») E lJIR(.r)). _ , of~.r») .. lilt cLau of .1Ifiln<_ A(t) suoh "'-- ~~ S ~ .. ~ far SOIfto1 CMSt:lltl
`C.'·III""n"CI. 1be IlSC orlbe "1""10. >IS" i, CIbIom.)'_ Knu,h pomo .... "'" tha, -mathc-mo""om, """""'""I)" """ Ihc - _
`.. !bey U>C
`Ihc won! 'is' ID f ... ,h"" Art>IO<tc. I> • nwt. bu' ....... ""~ n"""";l)" ,0.",,,,,1._--1"1
`
`Oth ~ r arit hmetic ol""nlol"5
`
`IIIg 0 1IOI>t_ can also be usallll ronjlllH.'tioo .. -,III """" ariIhmcuc ........ lors ID """" ."'''1'1 .... «"<1 oquol---. FOf oxamplo. A(xl· 0(/
`
`(~)) _os IlIo 00110<""" af Ii.on<t""" ha .... 'Il '110 _"t~ oflo(.» pi .... JW1 wltos<- _til IS 1;"\1100 '" I .... of)l.<). llt ....
`
`g(.r ) = h (~) + O(/(.r))
`.'presses ..... "'" as
`g(~) - h(z) - O(f(z).
`
`Page 5 of \3
`file JIfC:JUseT"SlklaiA DataiLocalfTem W2EIM09.hlm
`
`911 5120] S
`
`

`
`Big 0 notation - Wikipedia. the rree encyclopedia
`
`Pase 6 or IJ
`
`SuPf'O>C ..... """hm i> IxuJs .k-.'l:1opcJ II> ~.,. ...... of ~ dcmrnt •. I,..k-.'<'Iop<n..., "" ... nI"" tD fmdUlS. fun<I"", 7t~) ,ha,
`will "XI'«"> IIow bg Iht alpem .. ;11\31;. '0 nm (i~ ... n" arbilmy ""'_ ........ or,;..,.,) in """'" of"'" """,bot- of ............ in "'"
`""" • k""",,, ,..,., «Irnpl<x~y ofO{.n. .od ofl..-r ,ho ._'n< NR> "'" oleOfllhm ...... ""'. on ad/i"onaI 5s...' ~ 2.> ~ 10",""" bof"", "
`.. pol ><l. 1"'" oI".-i'hm ,,-.n. by r .... <011l1li" ......... ,"" 10 "'" "'" de""",,, in tho ..... 0I>d the ... perron.. ," 0-"" op<nt"""'- 1"'" "'"
`
`""""na'os. "Thus "'" ","<RII '''''' compI., "y oflhe "!IOOthn, """ ho ""~ .. 1\ .. ) - 5s...' • O(~'), 11=,be """"" 2w-IO ore
`>Uh<umtd ",'h1~ lbo f"' .... -_",~ O(~'), Apm. th.n .. !!" disn::Ilmil "'III.,,,fl"" r""",,1 """n'!lg of tho -.. '),"'001. "'" ;. does
`. 110,,· one II> "'" II>< bi~ 0 """'''''''' ... klOd of """,>mim, r1occbokltT.
`
`D«tal'lll lio" oh 'ariobt es
`
`AnoIt..T fal\ln: of,1>; DOlaI .... _gil 1= <.'I<:qO.1OnoI . i< !hal r.-:.IOIII 0Jiwnrnl> .... y """" '" be mfcm:d from II>< .-no .. 11m
`"" ... -rn ,....-,,,,,, an- im'oh'<'<1 n.. follow'Ri "'" np".hood side 110, 0 """'""'" ha,,, ...... 'ie .. ly dtlla-ml "",oninp:
`J(m) = O(m- ).
`g(n) = O(m").
`,10,,,.( .. ) nbibi" 1.,ly'U1"'" ¥'''''' ~, . ",hik: Ib< ....... "'oJ. """"', .... _" I. >l."", ,, .. 11(,,) ""hi IIi" """"""",, .. I
`nO\: fi'>I c_ ... b
`F"'1h. To .. <>0<1 ooolUs-' """'" auIbon; -= Ibc...-IOO
`g(1") _ O{/(1"».
`
`g=O(/).
`
`Muh iptf usages
`I" "»n: ~"" ""'ge.O( ) con oppoot '" d.1I<n-n1 rlOOd .... equal,,,,,. ~~ "", ...... 11,""" on _~."'" F<>r <!'>"'I"". Ih::
`(oI"'''''~"",lJUcf'''n -+ 00
`(n + 1)' = II' +O(n)
`( n + O( n' ~» )( n + 0 (1og II»' = ,,~+ 0 (,,512)
`" otl ) = O (e ft
`
`).
`
`'Tho mea""" of "",h .,."""""'" .. ao (0110-.. .. : fo.- -" fun<100ru ,,""--... ",,,.fy "",h 0( ... 1 <XI the I<tl.u. """'" "'" _
`fiID<I"",.
`""I>r:,'lIIg _h 0( ... ) on the rip.;!t<I<. >ocb thai """"'UlIng all "'"'"' r"""iJOO> ,010 tb< equation """'eo Ibt "'" SId<,-, equal for
`."""",1<.'" ""'" ...... '"'" _.., m,,,,,,," -For OIl)' NncI""'A~) - 0(1). IlI<n: ;. """'" r""",,,,,, I'<~) -O(e")...,h 11101 ,/"J - 1'<_)'- I"
`,mn; oI" llIe -"n """"100- oIxn-.; Ibt m."",, "1 ...... ,Ibt d.", "ff--,lOOc f<]OC><nl<'d b)'11Ie left >dt,.. !iUI»ct "rlh:: < .... of
`func'IOD> l<'JftS"'IIe-d by tho npo "do. In du • ..,., tho ..... b • formal ')'mboi,haI ... lIk. ""' "' .... J """ of ..... IS "'" • '}'1IIIIIrIJlc .-.lollOlL
`T1IUS IUt ~"""""" ~"I" - O(¥") ,b,. ' .... ;,'~'Iy "'" r ...... >Ial,,, .. ,. O(¥") '" ."1"
`
`Orders of common fun ctions
`
`11"'0 IS . IISI of d .. "" off\n:t"""" !hal on: _y .""''''''' ........ " 'hen .""IF"" lilt """'1f1$ ""1< ohn .Igonlhm. In ...,., .... , " IS
`• COO>I.1IIl 0I>d ... ,«co'"'" ".,_ bound. 1"'" """' ..... 1I"""1H~ r..,.,.""", on: g<t>CTally ~_ fJ .....
`
`Page 6 of \3
`file JIfC:JUst:T"SlklaiA DmaiLoca lfTem W2 EIM09.hlm
`
`91151201 5
`
`

`
`Big 0 notation - Wikipedia. the free encyclopedia
`
`Pase 7 o f IJ
`
`J "-
`
`O(JogIot; n)
`
`O((logn)J. c> I
`rO(,,'), O < C < !
`
`0(/1)
`
`0(,,1og- ,,)
`
`[ u "'pt.
`Ilct<'ffilUIoog ,r a bmary Rllmb ... IS ......... ,.. <><hl. CakuIau"l! ( _ \ )-, u."IIj! •
`""""""'"""" _",I.llIe
`NUlltller "r ~ ""' .... r""""" on il ..... I.I>oq """"",b'ion ,.,..,h in •
`"",cd orny of"";fonnly di,.uibul<d ,;>I"".
`I nn",ng .. ..... '" a ,.", .... IIfT.y .. nl~ " ""'"'Y ~ (II • !xl!.>"" ....... .m. ,,"" OS
`l"dl ..... I ___ "''' Ih~ ""~
`Matrix chain ordonng can b., 0<>1,"«1 UI poly1opntbml< "nil: on " I'anlIollUnOOrro
`A"""",Mach..,.
`Seart:htrq; ,n. kd-u¢<
`____ ,.,~::;=."=~, y; odillrq; 'wo ~.boIlIIIq;"'" by ripple <an)'
`t'~liIit'~ .. , "I"" in "'"'ISUlIl'll H, .... ",,,lr,,,,,...,j II .. (,,"'" .:as<) (II in:at -
`PorfuRnins INIlgulnion of • .u..,.. polYS"" lI<inI s..tder. algorithm. ,.. tho
`D.
`if .. < !
`-
`if n> !
`! +Iog-(Iog n).
`
`1-
`
`• ""' ...... n
`
`",,;'m ';"" aI~N''''''''''Iog· ( ,, )..
`
`(
`
`t-,thml<.
`0[ .. log n) = O[log nl) Iopi..,. . .,.
`qua<i!i""..-
`
`r ... fURn'''I! • r.s. 1'0""'" ' ...... ronn: btapsort. quookso:.11b<. ... 0UId "'''''"¥''" oas<).
`umcrg<:-""l
`
`Muhiplytl>j! " ... ......JoP' numbors by" .. ml'le .I~ bubble -""l ( .. "", c."" Of
`... It·. Ilnp .... """"""""'). Shdl ...... qw<bon I""'" ~~ ",Ie",,,,,,, _
`,..
`1Jt>iC11 __
`
`p<>/)""""".I ,.. -.
`
`0(n1. c > !
`£'.[0 .<:1. 0 < 0 < I ""
`c, .... ""U{ .. _I"{Oo" "1'-·
`O(c"), c> 1
`
`The: st. """"", 1(") = O( "r)" ""''''',,''''< tt·cata.:.llo 1(") = 0 (,,-) '" dm,,, _lor f"", ... ~ lOt OSI'mplOlJC """l!kx,ly.
`t·or ""Y~. > 00Uld C > (). 0( ,,« Jog .. t) IS • """'" or O ( " .... 1 KIf ""y , > (). '" may "" oonsodo=d aU rot,..,...... ",'" S<lm<
`biu<.T <>nIa-
`
`Related asYlIllltotic notations
`Bijl 0 IS lbt ""'" oomlOOllly lOS<\J >Slml'lo" " '.01.'''"" for COOIPWlIII! /Unc""""- .~hou&h ,n """,y ""'" !log 0 may be .-.pIa<:eoJ ""h
`n IB Theta 8 roo- OS}mp"""""ly "gill", bounIk... Ikn. ".~ del' ... """'" rrlatro ""la,,,,,,, .. tem .. orn'M O. """"""iog "p II> "'" filmily
`of ll.du,..",, -lM>diou _,..-10 ... h",h IkB 0 """",,,,,, beloop..
`
`Liulr-o ."lalion
`
`lhc 'nfonnal ......-nkoIt ~~) " 111,10-0 of g(x)" i. IOrmolly tt"ri!'onhl - <>(g(x)~ '" ..... not.otioohl E o(g(>")l. Inluitiwly. """"""
`..(r). Of ,imiIatty. tIuo tho grottth of.,(r ) ~ IIOltunM "","""",<!II 10 IIW of 1!C>l- 11 a<sU""'" -1-' g ....
`thai g(.T) IJOI's nlUth rasler -
`both fllrK"hllll> of ""'" ,-_10. ronnally.JI~) . <>(g(~))("'fi~) E <>(g(~))) .s n _ <» m<an. tha, fur ... ny pooilive e ........ & men,
`exi>!, • <1lD>bII1 N . ",h lh>I
`
`1/ (" )1::: ~ 1g( II }1
`
`for an II ~ II' .1<1
`
`Page 7 of \3
`file JIfC:JUSCT"SIklaiA DmaiLocalfTem W2 EIM09.hlm
`
`911 5120] S
`
`

`
`Big 0 notation - Wikipedia. the free encyclopedia
`
`Pase 8 of IJ
`
`NOI< ,I>< dilT<InI«O I><,,,,<CD tbc <artier fonna! d<fmllK>n f..- th< ,",-0 """".ion. ond II>< prn<nl dcfrnouon oflu.k.." ""bik II>< fOfTOCr
`1m to I>< ,0>: tor Olio",' ~ C<Jmlan.!of ,I>< lana"""" hold tor ~...,' po>.l'I\.., """""'" .. ho-...,'-a ..... n 1'1 In thi. ,...y bUk", 00<:1,;00
`tbc: =rr"'fl<>Dolurll ",,-0 ""'"'~ ~-cry func,ion tbOI .. Irnlc-o of /lIS _
`m.l<<s _ """'F' """c",,,,III _
`"'11-0 of /I. "'" _ "'-cry
`{""""on ,hoi ,. "",-0 /I .... .., ""~ of 1/ (for __ ~ II """If" ""~ .we.. i, " oJrnt...-ally <I,m .... r oo).
`
`f (rl
`.
`lim -() = 0.
`,-X> 9 Z
`
`Ln,l< 0 """""'" .. ron"""" _ rnaI-..'''''' hut......- m <OmpUIer .... O<t><e. In rompu1or S<O<n<e "'" _~ (ond f"""'"", _-Hoo) ,,"_
`otlcn • ""' .... Q""-.h«. In .-hoouI ..... the ,"2ri>bk ond func'- ,-..I".. are oft .. 1n!...,1h<n. JI>< """""llg 1"""""'" (~ in
`
`tbc ""'"' m:cDl. ><I.~_ """"oon) cu I>< lI!d'ul.
`
`c· o(f) = o(f) f<>rc '" 0
`0(/)0(9) £ o(f9)
`<>t<>tnJ < <>til
`o(f) c OU ) (and 'h .... 1>< obov.: ~ "I'!'ly \\'lIb _
`""""',n:uions of 0 ItId 0 ),
`-f(:r) .. o(g(r)r i •• "....ty .. "n .. os f{..-) = o(g(xn "hod! """'" """',do< ........ of
`
`A>; \\'j,h ,,",0 n<U'MlR. ,ho ... _
`-,~
`
`Big Om~a nOlat ion
`
`f (7) = n(g(z)) (7 --+ a).
`"",I numbol-..... Of __ , ,,'h<rr/-.l /I'''' ,.,.1 f_ dtr,lICd ,n 0 ...,i!/Ibo"""""-l o f or . .... \\'h<-rt /I I> po>.lh'''' on thl>
`who. ... " .. _
`""iglrto.hood.
`11k: fi"".-o (ehronoIo~Ay) .. used in ""'lyI'" _ r ,1Io<lo-y ..... die: OIho-r 011< III ~.,oonal ~I)' '1Io<lo-y \\ ...... tbc '\\"0
`>UI!it< .. """'~ Ilu, ",""' ..... IS bound 10 g ........ ..,.,flb"""
`
`f er) = n (g( r )) (..- --+ 00) .. 1i~~pl ~i;~1 > n
`Thus f er ) = fl(g(r )) ,.cbr: ~.""" uf f (..-) = o(g(..-)}
`
`f er ) = flll(g(r » (7 -+ 00)
`
`f er )
`.
`.. lim slLp - ( ) > n
`-
`or
`f ez) = fl~Lg(r)) (..- --+ 00) .. lilll inf f «(X)) < •
`, - 9 r
`
`Page 8 of J3
`file JIfC:JUseT"SlklaiA DmalLocalfTem W2 EIM09.hlm
`
`9115120] S
`
`

`
`Big 0 notation - Wikipedia. the free encyclopedia
`
`Pase 90f IJ
`
`fill II<arno 0.... and i'lL """ .. ,., i'l_
`l"""'" lin<' i)_I< I'l. I'l~ . fI_ IS "-ell os I {r ) = fI,. (9(r ))C .... "lIIIlIIl! lb., I (z ) = 0 +(9(Z))and I (r) = 0 _ (9(r»'rc
`
`too.h oat"r.:.!). are "",,' o .. m ndy.....J In 0".1), .. ....,.,.,., liIo<Jfy''''
`
`Simplr ~'-"""""
`
`sinz = O( I) (z -+ 00).
`
`ond """'" pmru<"ty
`sinz = 0 ,.(1) (z -+ (0).
`II'" h . ....
`
`sinr + 1 = U(I) (z -+ (0),
`
`~;nr + I = O ,( I){r ..... (0);
`
`In 1976 D.E. Knuth publis.hod a ~ '0 illSlofy "" ...., of II>< n-.~ '0 de...-nl>< o""",,~ I""I><"Y- """'Ih ,...IlIe: -F"nU th<
`"I'!'li<o'ion< 1 """e ""'" .., r. .. OO~,",,"'i~ •• >Ifong'''' '"'1, ...... <.11[ ... ' """"'" """" "I'f'<"I'fU"t". II. okfoned
`I (x ) = 0(9(-")) COO 9(7 ) = O{ / (r»
`
`" ',Ih ,t.: 0_ . -AhIlou@llIM''' oliarlj!",,1l1>rdyandL,I1k:'''·'''''''''d<1irulionorn. I rcd J"" .. /i«i ill ~ '" 1>«.""", u..:~
`doro"""", Ii by "" nnm II ",-,ok usc. olld b<cott\(: lliao I.!< <>!ba " -oys 10 "'Y '" hallb<y .. -ant 10 ... y II 11>< ~I"l;"/y """ ~
`" bon Ih<1r dof ... l.,. .ppl;"'~ ,," U"",-..""". thr lURly-UI1Ic'wood dof"",JOO had bem uoaI ("ul loa,!. 25 )"<WO-""
`
`Page 9 of \3
`file J/fC:JUsenlklaiA DmalLocalfTem W2 EIt.l09.hlm
`
`91151201 5
`
`

`
`Big 0 notation - Wikipedia. the free encyclopedia
`
`Page IOofU
`
`Fa mil)' o r Blc"m R n n-Lln d~ u nota tions
`
`I :-; ..... ' tn,u l,ion
`
`t. rnem.t dcf .. i ...... , rn •
`• "rr-d .. 'ly l ..... n __
`
`If{n)1 !:> l' ·lg(n)I "" som<
`1"""''''' k
`
`3k > 0 3"0 'rIn > "0 1f(") I!:> k ·lg(,,)1
`
`T .. ·•
`"'l1nl" .. n. ,
`
`f ( n ) ;?: I; • g( n) D- rnflllildy
`"""'Y , .. h, .. or ~ 0Ild ........ \1'"
`po>if""' k
`
`Numba- th<.lry:
`3l: > 0 'rIno 3r1 > no f (n);?: l" y(n)
`
`f (n ) ;?: I; . g( n) b """"
`POS""" k
`
`f (n) = O(g(n» ~
`
`C."nr" .. i,y -/
`
`IS boIm,l<,"
`btIo\\' by ,q
`")"'I'"",o.11y
`
`f (n) = e {g(n» .I~
`
`'"'"
`/-
`dom. .. ted by 1f t n)1 !:> l' 'Ig( n)~ for c",",),
`f (II)=o(g( n» ~~ .. II
`feud JlOSI<'ve numb<t k
`9
`'"
`.. YlIlfl"",..,,11y
`/ dott" .... , .. 9 1ft n)1 2: ~. -Ig( n n f"".-,',",),
`f (n) = (.)(g(n» ~
`OSj'Ol",,,,,,,,,,11y (...00 "",iti." IIUIDIt<t- k
`
`f( II )"" g(1I)
`
`/"<q.Jaltog f(n)IJ")~ I
`",)"""IOI,,,,,11y
`!I\
`
`Vk > 0 3"0 'rIn > 110 If(n) l!:> k ·19(,,)1
`
`Vk > 0 3no 'rIn > no 1/ (n)l2: k '1g(1I)1
`
`A,HI< lrom Ilk Bi~ U _ - . Ibc: B'g Th"" e ODd Bi~ C!ruql. rl """",ion<",,, ......... " """" o Hm -.J 10 """1'"'" ..-inK<.-: tbe ... >all
`"""'p m -...",.. is o.'c....-lly.....t incompul<lonm«.
`A,Hk from tbc B,S 0 _ - . Ibc: ,.".11 0, 11'8 0In0<p rl .00 .... _
`onq . .. now"", is "',,-.. ""'" fa IIUIIlber lhoory.
`
`an: tbe tt.a.- . - ofkn -.J .. "urn"',. lhrory: Ih< ",,"II
`
`Ust in {omputt r scit nn
`
`r"""li<oI1t~) .. 13..-' • 22.0' ~ ~. all 0( ,11< rot .......... ar. generally *""qUblc, but hp.kf "'"-"'<Is (i.., .. _-rs Z ODd J bc:bv.') .. ~
`
`I"r""","uy, ~lIy in «><npUI'" ""0<11«, tbe Hog 0 """""'" oli ..... pcrrnHt,,, to be .o .... ".-ha, obu>aJ to describe ... a!iyatplOllC 'igh!
`bound " '!on<: u.mg Rig Theta 8 _tim mi[<ho. be more r ... ,uaIly..,.-.rorriatc m oBi''''' """'~." . FOI ~. ,"'hen rooo.idcring a
`...... lly --slY ",denal "''CI Iooo.T bound. (i.c •. lIllIIIl><f 1 bcbv.").
`
`t , 1l~) . 0I.~-'
`
`PagelOofl3
`fileJlfC:JUseT"SlklaiA DalaiLocalfTt:'nJ W2 EIM09.hlm
`
`911 51201 5
`
`

`
`Big 0 notation - Wikipedia. the free encyclopedia
`
`Page II of IJ
`
`~. 7l.~) - 0(~')
`3 Jt,,) - 8(~')
`
`Tbc cqu .... lcnl l:ngl'sh .I • ..",.". ... ~ ""'I><"1"""'Y
`l. n .. )_~ as)mpI<>IoaIlyDO f .......... n ...
`2. 7t .. )_~ .. ) .... 1pIOIoaIlyno f ... ", .... n ...
`3. n .. ) _~ aspn","''''''11y as f ... os .. '.
`So whole . 111hRoo ,;Ia(c-merns..., 1rV<. ~,'dy ""'"' in f~ioo """"""ned ... _Ii. In """'" fi<'Id.. ....... ~"'. ,lot Ii'~ 0 """"k'"
`("un,"'" ~ ... 11>< IISIS obo'"<:) ""OUld be u,;«[ . - . O<ImIt'I<lIlly !ban doc Ilog n"."" nooallO)l1 (bulk.1. nornton .J UlIIk: li~ oto<ro"J. fot
`""'lIP". IfJt_) rt1""scnb Iho "",",ng I ..... Df 1 _fy """,loped alj!OI1lhm foc 'npIIl""" ~. Ilk: '"' .... Ion ~ uS<r.< Df\ht a1l!ori1lun
`mi!j.h' lot """" "",toned 10 pili _ ~ as~mpotl< bound on -Imf. il .. ill ,oI:c: II> "'" ... "bool moIuDf. ... c~"Ii<:n SUIm>nII """", ,II<
`k ...... <~ OS)~ """nd.
`
`E ~ lension5 10 Ihe Ba(hma n n--Landau nOlalio ns
`AnoIho:r -...on ."meUm<> _m <:OIl"""'" ><.'ICIIC<: ,,{j (n:ad ~-O):j(n) - O(g(_)) .. .JJonOand fOl)l_1 - ~~) lot' gt.)) for
`""''''' k. EMm\,aUy. " .. H'g 0 ...,..ion. ign<lfUlllopnlluni< fOClOn boca"", Ilk: ,...,..lh-n1o .rrett' of"""" "' ... ~ >UJIIT·1opnIluni<
`funo'ion __ a 11"",,110-.- np-' for IarJ!c-Mlcd inp .. ~ thln '" men: ....,.,.wu to ~ bo.i.I ....... tim<
`I""f....,......, than II", fi"",-p>m1 ill""", o;<>nlri_..,. ,be Iopritlani<-J!f"",h faclOl(.). 'I'lu. "",.""" .. 0 0"" u.oo to ""' ..... ,lot
`"ttilpock ..... " ',do", g", ... ,II-<a&eo 1M .,.~ "ak<I OS 100 u!!.luly Ixtund.-d ,..,.. tit. "Ian ... lit band I"""" ........ t" .. ys «of) ror ""Y
`Illy C > 0).
`roo"uo,.t _
`
`"Iso lbe L .. " ........ Ikfin«l ..
`
`Generalizations and related usages
`'Th< 8~ 10 f""""-< r&ing , .. I"", in.ry nonro<d ,'a._ >f'O"<' 's sJra,ghllOno.-.d ('<!,i.xint _
`.. "'I .... ..,. _ J.
`wht-n:/ ODd" ..,..."j no! tHe the.- ,-..I"", m llot ...... "f'K<'. " ,.......1;"'1I0Il l<, fun<!""", I i.alUl, , .. I..". on any ~ _
`" al",
`pos:;ibk. 1 .... "hmtl"lIl rn-: .... " co-.<, <lUI . Iso lot ~.li/"""" .. troduo,"g on """"nory filler base. ,.~. II> <Io=led _/andl!' Tbc "
`notalion .... lot ....,.) "' <lof ... doom'au,,," .nd diffCftftbability ,n qWI< , ....... 1 ""'"""'" _.oJ", (as)'m(II<ltlClf) cqu" ... ~ of fitnt:llOM.
`
`/-g -
`
`(f-g) Eo(g)
`a ",on: ~,'1: "",ion tboB 111< ",t.loono;!up 'li;, tits)" from _"./1, ,educes 10 I.m/l, -
`... ·Iri<b is ""'1,." .. 1<:"", .......... _
`and I!' on: P""""" ,cal , .. I"'" t-1""",,-) I'", <XOI1t!>k. J i;, 8(~). buI !< - ~ .. "'" «~)
`
`I if/
`
`tlistory (Bac hmann- Landau, Hardy, a nd Vinogrado,' notations)
`1 .... . ymboI 0 " ... fi ... in~ by nu,nhtJ thoon .. l'aul I~""""" ill 189-1. in Iho ...oond ",hi"", ofhi> boot "mIJ-
`/..,hl""'~ (" . .. 1).11< number Iboocy"). tho t .... ,-01 .. "., 01 " 'Ioch (not )~1 ~ bol! U '''''''''''''I ...... publ,>I'>ed .. IllY!,!''' I II<
`"",,,her tlI<cri" & lmW>J t...-bu adoJ>tru ,~ ..... " ... lit ... in"" .... II> inlrodu<:< ,~ 19(19 Iho ...... li"" <>-WI hrnc<: botb .... "",,' <all«!
`... ro.t:.u "lmbols. lhos< ...... ' ..... ,"'<'f¢ ....... ,n awl .... """""","10<0 ""fI"g (~. 11I50s fot' . ')'''''''''''' .... 1YM".t ' .. 'Th< bt~ O ... -as
`I"'I"'wuru ,m """1JIIl"" ........,., ..,. IJonald .......... ho "'·'n~ Iho "' ..... '<1 Omcp and ·1 ........ _
`"" Knullt...., -..J tbat
`,be Omcp ""'"""" Itod b..,.. .. noduo:<:d ..,. H ... ly ODd U """,...,J."' ......". • d,ff, ....... ...oanifijl "1<>- (.~ • .., no! .., Q 01"). ODd
`I'fOI'O'CIl tile ...... <lofinttlCG. 1 t.dy and l.ttlle-oo'OOd'. oo~il\3l deflll1'l011 (" 'h,ch " b.oJ"'....,.) tn one ~ by 1.andaJ"~ ,S !.till u;«l
`m """""" 1boc<J<y ,,,.bet"< Kn!ah'. <loflnltion ..... ,'" U>«l). In fact. .......... Iso u ...... 1924. on ,be fQP<'I ....... "",",ion«!. Iho ~'Iltbol.
`11 R ("rigbl"' _11,. (' 1<'11"). _1tscII _'ffi1 ,~in 1918 bj.· lIardy and l.inl""'OO(I.(1t1 and w1tk~ _= P!"I'IINOf$ fot' dIt """"'"'
`(-is not IaIgcr Ihan a .mall 0 oI"~ lbu.lll< Omega .ymboI. ,,,,lit Ihcu OIlguw
`. ymhol.O ... C"l> not >1OI11a' than . """,II ""I") ODd 0
`"""'"'Itg. ) Me """",,1JItS oho Kfcm:d 10 as -I ....... )mml,-
`
`"Iso. lzIdou ..... ...,. used lite B'II Tbc1. and ..... 1 """"" , )'mbob.
`
`Page I I of \3
`file JIfC:JUseT'SlklaiA DalaiLocalfTenJ W2 EIM09.hlm
`
`911 51201 5
`
`

`
`Big 0 notation - Wikipedia. the free encyclopedia
`
`Page 12 of IJ
`
`/~g _
`/EO{g).OO /-<g _
`(11Oldy """~'<I" D<V<T dctiD<d or....ro lbe n<UtiOIII ~ !\Of <. as i bas b<:<m """"" ..... rcponed~ II slIouId al"" be I>OO<d """'Ibrdy
`inlJ'oduces .... '}"'''''~' -(and -«(ao ,,'ell as..,.,.. oob<T .)"lbob) ;" bl> 1910 Ir3o<I "'Ord<rl< or !nfin~y". _ mak"" .... of II Oft!y in 'h"",
`I"'Il"f" ( 1910-1911). In hi, -1)-,j()Q I,""""ni"ll """"" .nd b<>::>I<. "" """'~I' .... I)- ...... do: 1.and3" '1-nbJk 0.00 o.
`
`/Eo(g);
`
`oumI><T Ihron\.l h .... ~\ah·"l~'>ch Vinognd<w
`1I:m1y'I ....... "'" LS DOl ".-.I aR}-. On 'Il< """'" ~ In "'" 19)(1<..'>01 "'" R_
`tn1~ III> ""'"""" <. " 'hodo bas b«-n Incra>IIII!ty ...ro In ........ 1hroIy , .... <ad ofd>< 0 ""'""""- We haw
`/ <g _
`/EO (g).
`
`n.: bl,!;.(l onpnoll)- >lanJs roo- "ookr 0, ("C/nInoIni-. 'Io>ch"",,"", 189-1). and IS ,''''''. roman ktl<f Neuhe,- Floo<hn""", _
`l.andou no
`.111 i, -OmI<l'OlL" 'Ille .)"tLLboI ..... n"",h I .... OIl (1976) ,'iowed by ""'--h .s I c.apollLl onua-on.'''' pn>IMI>Iy III ",r,..-.",.,. '" bl>
`oJo,fi,,;' ..... .,ra.. » '''~...t Oo''''p.. no: ~il!" ""' .. >IouuIoJ ",.ol 1", .........
`
`See also
`,\.)-mplt>I'" .. """""",, Appro>."""'''''' oIfunc1.<>n, ~'" Tlyh..-, r<>nllOlb
`M)-mplt>I","lIy "!""nal. A ph,-"". lk<I_ly uS«! '" dos<fib< ... ~lg"';I"'n """ has an lJIlP<I 00und ")'mpI<>Ii<ally ... "tun a
`r... lbc probktn
`~ of I 10'''<:' _
`II,S 0 .. prnbobili,y _I0Il' O,.a,
`Limi, ~ and lionic ... fai«: AD o:xpL.aoiooo of"""" of"'" limi' -..,;"'" LI>C'd in Ihi> ....... 10:
`N..:bb .. ·.lhoo".-,n: A pr«_ mclOOd of~ <:<>mpla ..a/yl1C f ..... ,""" "" lbo, lh<: <lorna,. of """""18"""" of "l<'p1IIl
`~r"""" .... be >laIcd
`
`References a nd Notes
`
`IJ~~~lhnP: _ .IfIOII<.rom·_ ·
`I""""""",, 1I<lP19I)O;:_:!O.IlIj, r.o·
`od"<ll-'oII)o,~ItPf PAm), Spnnp- p. m IsmI 9n.o.JaM7~l~
`.. r __ .~ 11,"I',. __ -"'.o>m ........... 1 :X'i:;sl>ql\.lC~ PA4~
`2. ~bol< Ililolno<-> IS I~ :'O12~ /"" .... _
`~ \'1'. 4 ISH:;>n3-1"'*14·~n-9
`. ~C_"I mC........,.oyThcay..dlto«q ..
`J
`),1 ..... _
`C ____ -(hI"""""' .... ___ ,«JdL'W"'IUi ... '~ . fodt) (PlJt). p. 2. R ........ "" 1 .tun< 201 4
`4 'n.,. ... II. Connon .. 01_ 2001 . l .. roW:_oo AlI<onIhm~ s-.d l'4oloo ("Ip' ~"",'·ho""'''''''''OO10UIJII')
`s. c.:.-a. n.om...; l<f...-.a...ks: Ill' nc. RooaIo1S ... on. a;1foN(!009~ fn_ .. ,t/gorl ..... (I_00J ), MI'T p. ~
`6. 1"'"'-.11. Rodn<y ""00 A_ Sotoo"",.lIb MulI>f'I< V_ - (hIfpJlpropk .... bo..odW-""",·,U"I_,p.!I} (""1- R ...... ·od
`20 I S--(J4.11
`7 ~ G .... 1lno~(l95I). AoJ ___ l /tl_ io AIdp/J (hiif" ~-"""""I __ ' IImV.~ICIt .. - rA"" '"Q-""
`~ 11"'_' 0>%12~ Ad> L,-.. :;"...1 __ PII. ' "7. ISH~911-O-1Il6--&1nl·'
`Gnhom, IJon.Id ..-. and 01\:. r .... _ (1n4~ ().201 _551O.l_' C_", ... .1 __ ... , (hnp-J _--'<.«Ld"
`8 _
`9 u.-wK.a (Juno ... '" 19\111). - r...,~c __ .""'Il"crtlLnpj .......... ,-.,.,..'-'I99ll()(;'_ =, po!f)(1'OFJ- .~o(lM
`od 1.-QAAAA.\~""'ISIl~)(!cd.) ~ Mao .. +- ~II" ",do.h_ "' • ....,. 1' . ... 6 ISOS91I-O-201·"8O.l-'l
`" - -JIiJ_1koI s..-~' 45 (6). 681. t~ , ........... (bup "".-. ........... lUIaoI'oIdcd<ol kn.aboca"'-""ll
`10. (]. Il l l.dy_ '. t: L>a .... - . -so.n.proILoI<-o(1loopI _ - . . . ... ""-.A<tIL _
`... J7(1~14).1' :':'5
`II (]. Ill!..ly""" 1. F~ Utdno.ood.. c,,,,,,-;buo_ to ... LIoo<:ry""'" _
`" .... r........ '"'" "'" ......,. ....... _"",_ ............. AM>
`.1I<ri<
`. 0. ",1. 41.1911.
`I:!. IlonaIoI ~ -Il~ o.--r... '"'" k g Om<p - ' m, 1'h<1o. (hllp:- .",-, .,"I,.o.nI'" ... ,""IO-l! _
`" -om ..... p.ll)". SlGACT
`Sn. .... ",," .. /_ 191fi. 1&,24.
`IJ. 1:.1 ......... -m..-,-"",_ ""Gil""p •• ,"" ...... -..-Ikon;:ka IV· S.d .. G«odI. "'c ..... Go'IIl, ~ 1(1. 11r.4. 1)7 1SG.
`
`..... 1 ___ ...... 9 JoM 1I"Ilcya:Soe-.I985 .
`14 AIebooodor I,lL!. The _
`IS. E.C- 1O ... !.noN\, 11>< ·I-,."r .... ~7 __ F ..... ion(Od."':a.m.Jon " - 19S1)
`16. ~_I '.p.n.II_o("4'rlII"'fonlw-w-IaJ ........ SlA"1 ISll'IG-M71 .. U0-6. r l5
`17 E.- '--". 1_ "" 1.<"'" ''''' .. \ ''''';)q <In rr--.. 1 __ • t....,J t9O'l. p.W
`19. s.. '" - . , -" ............. foo G.., .. "' .... ,., f"UI>Irm- (_~ lluklody AbIo:m. S ...... Ss.'iR ,. So ~ (19J.4~ !-I'J."')
`