Lecture Notes CMSC 251high school algebra. If c is a constant (does not depend on the summation index i) thennXi=1cai= cnXi=1aiandnXi=1(ai+ bi)=nXi=1ai+nXi=1bi.There are some particularly important summations, which you should probably commit to memory (orat least remember their asymptotic growth rates). If you want some practice with induction, the firsttwo are easy to prove by induction.Arithmetic Series: For n ≥ 0,nXi=1i =1+2+···+n=n(n+1)2=Θ(n2).Geometric Series: Let x 6=1be any constant (independent of i), then for n ≥ 0,nXi=0xi=1+x+x2+···+xn=xn+1− 1x − 1.If 0 <x<1then this is Θ(1), and if x>1, then this is Θ(xn).Harmonic Series: This arises often in probabilistic analyses of algorithms. For n ≥ 0,Hn=nXi=11i=1+12+13+···+1n≈ln n = Θ(ln n).Lecture 3: Summations and Analyzing Programs with Loops(Tuesday, Feb 3, 1998)Read: Chapt. 3 in CLR.Recap: Last time we presented an algorithm for the 2-dimensional maxima problem. Recall that the algo-rithm consisted of two nested loops. It looked something like this:Brute Force MaximaMaxima(int n, Point P[1..n]) {fori=1ton{...for j = 1 to n {......}}We were interested in measuring the worst-case running time of this algorithm as a function of theinput size, n. The stuff in the “...” hasbeen omitted because it is unimportant for the analysis.Last time we counted the number of times that the algorithm accessed a coordinate of any point. (Thiswas only one of many things that we could have chosen to count.) We showed that as a function of nin the worst case this quantity wasT (n)=4n2+2n.7Lecture Notes CMSC 251We were most interested in the growth rate for large values of n (since almost all algorithms run fastfor small values of n), so we were most interested in the 4n2term, which determines how the functiongrows asymptotically for large n. Also, we do not care about constant factors (because we wantedsimplicity and machine independence, and figured that the constant factors were better measured byimplementing the algorithm). So we can ignored the factor 4 and simply say that the algorithm’sworst-case running time grows asymptotically as n2, which we wrote as Θ(n2).In this and the next lecture we will consider the questions of (1) how is it that one goes about analyzingthe running time of an algorithm as function such as T (n) above, and (2) how does one arrive at asimple asymptotic expression for that running time.A Harder Example: Let’s consider another example. Again, we will ignore stuff that takes constant time(expressed as “...”inthecode below).A Not-So-Simple Example:for i = 1 to n { // assume that n is input size...for j = 1 to 2*i {...k=j;while (k >= 0) {...k=k-1;}}}How do we analyze the running time of an algorithm that has many complex nested loops? Theanswer is that we write out the loops as summations, and then try to solve the summations. Let I(),M(), T () be the running times for (one full execution of) the inner loop, middle loop, and the entireprogram. To convert the loops into summations, we work from the inside-out. Let’s consider one passthrough the innermost loop. The number of passes through the loop depends on j. It is executed fork = j, j −1,j−2,...,0, and the time spent inside the loop is a constant, so the total time is just j +1.We could attempt to arrive at this more formally by expressing this as a summation:I(j)=jXk=01=j+1Why the “1”? Because the stuff inside this loop takes constant time to execute. Why did we countup from 0 to j (and not down as the loop does?) The reason is that the mathematical notation forsummations always goes from low index to high, and since addition is commutative it does not matterin which order we do the addition.Now let us consider one pass through the middle loop. It’s running time is determined by i. Usingthe summation we derived above for the innermost loop, and the fact that this loop is executed for jrunning from 1 to 2i, it follows that the execution time isM(i)=2iXj=1I(j)=2iXj=1(j +1).Last time we gave the formula for the arithmetic series:nXi=1i =n(n +1)2.8Lecture Notes CMSC 251Our sum is not quite of the right form, but we can split it into two sums:M(i)=2iXj=1j +2iXj=11.The latter sum is clearly just 2i. The former is an arithmetic series, and so we find can plug in 2i for n,and j for i in the formula above to yield the value:M(i)=2i(2i +1)2+2i=4i2+2i+4i2=2i2+3i.Now, for the outermost sum and the running time of the entire algorithm we haveT (n)=nXi=1(2i2+3i).Splitting this up (by the linearity of addition) we haveT (n)=2nXi=1i2+3nXi=1i.The latter sum is another arithmetic series, which we can solve by the formula above as n(n +1)/2.The former summationPni=1i2is not one that we have seen before. Later, we’ll show the following.Quadratic Series: For n ≥ 0.nXi=1i2=1+4+9+···+n2=2n3+3n2+n6.Assuming this fact for now, we conclude that the total running time is:T (n)=22n3+3n2+n6+3n(n+1)2,which after some algebraic manipulations givesT (n)=4n3+15n2+11n6.As before, we ignore all but the fastest growing term 4n3/6, and ignore constant factors, so the totalrunning time is Θ(n3).Solving Summations: In the example above, we saw an unfamiliar summation,Pni=1i2, which we claimedcould be solved in closed form as:nXi=1i2=2n3+3n2+n6.Solving a summation in closed-form means that you can write an exact formula for the summationwithout any embedded summations or asymptotic terms. In general, when you are presented with anunfamiliar summation, how do you approach solving it, or if not solving it in closed form, at leastgetting an asymptotic approximation. Here are a few ideas.9Lecture Notes CMSC 251Use crude bounds: One of the simples approaches, that usually works for arriving at asymptoticbounds is to replace every term in the summation with a simple upper bound. For example,inPni=1i2we could replace every term of the summation by the largest term. This would givenXi=1i2≤nXi=1n2= n3.Notice that this is asymptotically equal to the formula, since both are Θ(n3).This technique works pretty well with relatively slow growing functions (e.g., anything growingmore slowly than than a polynomial, that is, icfor some constant c). It does not give good boundswith faster growing functions, such as an exponential function like 2i.Approximate using integrals: Integration and summation are closely related. (Integration is in somesense a continuous form of summation.) Here is a handy formula. Let f(x) be any monotonicallyincreasing function (the