Lecture Notes CMSC 251 high school algebra If c is a constant does not depend on the summation index i then n X cai c n X i 1 ai n X and i 1 ai bi i 1 n X i 1 ai n X bi i 1 There are some particularly important summations which you should probably commit to memory or at least remember their asymptotic growth rates If you want some practice with induction the first two are easy to prove by induction Arithmetic Series For n 0 n X i 1 2 n i 1 n n 1 n2 2 Geometric Series Let x 6 1 be any constant independent of i then for n 0 n X xi 1 x x2 xn i 0 xn 1 1 x 1 If 0 x 1 then 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 n X 1 i 1 i 1 1 1 1 ln n ln n 2 3 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 algorithm consisted of two nested loops It looked something like this Brute Force Maxima Maxima int n Point P 1 n for i 1 to n for j 1 to n We were interested in measuring the worst case running time of this algorithm as a function of the input size n The stuff in the has been 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 This was only one of many things that we could have chosen to count We showed that as a function of n in the worst case this quantity was T n 4n2 2n 7 Lecture Notes CMSC 251 We were most interested in the growth rate for large values of n since almost all algorithms run fast for small values of n so we were most interested in the 4n2 term which determines how the function grows asymptotically for large n Also we do not care about constant factors because we wanted simplicity and machine independence and figured that the constant factors were better measured by implementing the algorithm So we can ignored the factor 4 and simply say that the algorithm s worst 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 analyzing the running time of an algorithm as function such as T n above and 2 how does one arrive at a simple 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 in the code below A Not So Simple Example for i 1 to n for j 1 to 2 i k j while k 0 k k 1 assume that n is input size How do we analyze the running time of an algorithm that has many complex nested loops The answer 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 entire program To convert the loops into summations we work from the inside out Let s consider one pass through the innermost loop The number of passes through the loop depends on j It is executed for k 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 j X I j 1 j 1 k 0 Why the 1 Because the stuff inside this loop takes constant time to execute Why did we count up from 0 to j and not down as the loop does The reason is that the mathematical notation for summations always goes from low index to high and since addition is commutative it does not matter in which order we do the addition Now let us consider one pass through the middle loop It s running time is determined by i Using the summation we derived above for the innermost loop and the fact that this loop is executed for j running from 1 to 2i it follows that the execution time is M i 2i X I j j 1 2i X j 1 j 1 Last time we gave the formula for the arithmetic series n X i i 1 8 n n 1 2 Lecture Notes CMSC 251 Our sum is not quite of the right form but we can split it into two sums M i 2i X j j 1 2i X 1 j 1 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 4i2 2i 4i 2i 2i 1 2i 2i2 3i 2 2 Now for the outermost sum and the running time of the entire algorithm we have T n n X 2i2 3i i 1 Splitting this up by the linearity of addition we have T n 2 n X i 1 i2 3 n X i i 1 The latter sum is another series which we can solve by the formula above as n n 1 2 Parithmetic n The former summation i 1 i2 is not one that we have seen before Later we ll show the following Quadratic Series For n 0 n X i2 1 4 9 n2 i 1 2n3 3n2 n 6 Assuming this fact for now we conclude that the total running time is T n 2 n n 1 2n3 3n2 n 3 6 2 which after some algebraic manipulations gives T n 4n3 15n2 11n 6 As before we ignore all but the fastest growing term 4n3 6 and ignore constant factors so the total running time is n3 Pn Solving Summations In the example above we saw an unfamiliar summation i 1 i2 which we claimed could be solved in closed form as n X i 1 i2 2n3 3n2 n 6 Solving a summation in closed form means that you can write an exact formula for the summation without any embedded summations or asymptotic terms In general when you are presented with an unfamiliar summation how do you approach solving it or if not solving it in closed form at least getting an asymptotic approximation Here are a few ideas 9 Lecture Notes CMSC 251 Use crude bounds One of the simples approaches that usually works for arriving at asymptotic bounds Pn is to replace every term in the summation with a simple upper bound For example in i …