Design and Analysis of AlgorithmsMath review 1Mathematical InductionLogarithmsOtherSimple SeriesL’Hopital’s Rule:Review of limitsReview of derivativesCS333Fall 2001CutlerDesign and Analysis of AlgorithmsMath review 1Mathematical Inductionhttp://www.purplemath.com/modules/inductn.htmLogarithms)lg(lglglg)(loglogloglnloglglogloglogloglogloglog)(logloglog)(log2loglognnnnxxxxyxaxxxyxyxyxyxxykkexybbaayaaaaaaabbhttp://www.purplemath.com/modules/logs.htmOthernmnmnm modSimple Series1. Arithmetic series: The first n values are: a, a + d, a + 2d, …, a + (n – 1)d where a is an initial value and d is a fixed increment. The sum of the first n values is:2))1(2(10ndnaidani.2. Geometric series: The first n values are: a, ar, ar2,…,arn -1 where a is an initial value and r 1 is a fixed multiplier. The sum of the first n values is:rraarnnii1)1(10. When -1< r <1 and r 1 the sum of the infinite geometric 1CS333Fall 2001Cutlerprogression converges to: raarii10.3. Harmonic series: The first n values are: 1, 1/2, 1/3,…,1/n. The sum of the first n values is: Hn = 1+ 1/2 + 1/3 +…+ 1/n satisfies nHnnln1)1ln( .Arithmetic and geometric progressionsL’Hopital’s Rule: If f(x) and g(x) are both differentiablewith derivatives f(x) and g(x), respectively, and if thenwhenever the limit on the right existslim ( ) lim ( )lim( )( )lim'( )'( )x xx xf x g xg xf xg xf x Review of limitslim ( ), .x cf x lf(x)-l iff for each there exists > 0 such that if 0 < x - c then 0If lim and lim then: a) [ ] b) for any real c) [ ] d) If then lim and limx c x cx c x c f(x)=l g(x)=mf(x)+g(x) =l+maf(x) al af(x)g x lmmg(x)=mf(x)g(x)=lmx cx cx climlimlim ( )01 12CS333Fall 2001CutlerReview of derivativesp x xfg x f x g x g x f xfgxg x f x f x g xg xddxf g f g x g xddxxxddxe eddxe e f xddxp p pddxpnx xf x f xx xg x( )( )'( ) ( ) '( ) ( ) '( )( )'( )( ) '( ) ( ) '( )[ ( )]( ( )) '( ( )) '( )ln( )( ) '( )( ) ln[( ) ( )( then p'(x) = nx for nn-1012) ( )] '( ) ln(log )ln(log ( ))'( )( )lnp g x pddxxx pddxg xg xg x pg
View Full Document
Unlocking...