Theoretical ComputerScience Cheat Sheet

Theoretical computer Science Cheat SheetDefinitionsSeriesf(n) =O(g(n))iff positivec, n0such that0 f(n) cg(n) n (n+ 1)2,nXi=1i2=n(n+ 1)(2n+ 1)6,nXi=1i3=n2(n+ 1) general:nXi=1im=1m+ 1 (n+ 1)m+1 1 nXi=1 (i+ 1)m+1 im+1 (m+ 1)im n 1Xi=1im=1m+ 1mXk=0 m+ 1k Bknm+1 series:nXi=0ci=cn+1 1c 1, c6= 1, Xi=0ci=11 c, Xi=1ci=c1 c,|c|<1,nXi=0ici=ncn+2 (n+ 1)cn+1+c(c 1)2, c6= 1, Xi=0ici=c(1 c)2,|c|< series:Hn=nXi=11i,nXi=1iHi=n(n+ 1)2Hn n(n 1) (n+ 1)Hn n,nXi=1 im Hi= n+ 1m+ 1 Hn+1 1m+ 1 .f(n) = (g(n))iff positivec, n0such thatf(n) cg(n) 0 n (n) = (g(n))ifff(n) =O(g(n)) andf(n) = (g(n)).f(n) =o(g(n))iff limn f(n)/g(n) = an=aiff >0, n0such that|an a|< , n Rsuch thatb s, s Rsuch thatb s, s infn anlimn inf{ai|i n, i N}.

Theoretical Computer Science Cheat Sheet π ≈ 3.14159, e ≈ 2.71828, γ ≈ 0.57721, φ = 1+ √ 5 2 ≈ 1.61803, φˆ = 1− √ 5 2 ≈ −.61803 i 2i pi General Probability 1 2 2 Bernoulli Numbers (Bi = 0, odd i 6= 1): B 0 = 1, B 1 = −1 2, B 2 = 1 6, B 4 = − 1 30,

Loading..

Tags:

  Computer, Sheet, Teach, Cheat sheet

Information

Related search queries