Lecture Notes CMSC 251 We have this messy summation to solve though First observe that the value n remains constant throughout the sum and so we can pull it out front Also note that we can write 3i 4i and 3 4 i T n n log4 3 log4 n 1 X n i 0 3 4 i Note that this is a geometric series We may apply the formula for the geometric series which gave in an earlier lecture For x 6 1 m X xm 1 1 xi x 1 i 0 In this case x 3 4 and m log4 n 1 We get T n nlog4 3 n 3 4 log4 n 1 3 4 1 Applying our favorite log identity once more to the expression in the numerator with a 3 4 and b 4 we get 3 4 log4 n nlog4 3 4 n log4 3 log4 4 n log4 3 1 nlog4 3 n If we plug this back in we have T n nlog4 3 n 1 3 4 1 nlog4 3 n nlog4 3 1 4 n log4 3 n nlog4 3 4 nlog4 3 n nlog4 3 4 n nlog4 3 4n 3nlog4 3 So the final result at last is T n 4n 3nlog4 3 4n 3n0 79 n It is interesting to note the unusual exponent of log4 3 0 79 We have seen that two nested loops typically leads to n2 time and three nested loops typically leads to n3 time so it seems remarkable that we could generate a strange exponent like 0 79 as part of a running time However as we shall see this is often the case in divide and conquer recurrences Lecture 8 More on Recurrences Thursday Feb 19 1998 Read Chapt 4 on recurrences skip Section 4 4 Recap Last time we discussed recurrences that is functions that are defined recursively We discussed their importance in analyzing divide and conquer algorithms We also discussed two methods for solving recurrences namely guess and verify by induction and iteration These are both very powerful methods but they are quite mechanical and it is difficult to get a quick and intuitive sense of what is going on in the recurrence Today we will discuss two more techniques for solving recurrences The first provides a way of visualizing recurrences and the second called the Master Theorem is a method of solving many recurrences that arise in divide and conquer applications 27 Lecture Notes CMSC 251 Visualizing Recurrences Using the Recursion Tree Iteration is a very powerful technique for solving recurrences But it is easy to get lost in all the symbolic manipulations and lose sight of what is going on Here is a nice way to visualize what is going on in iteration We can describe any recurrence in terms of a tree where each expansion of the recurrence takes us one level deeper in the tree Recall that the recurrence for MergeSort which we simplified by assuming that n is a power of 2 and hence could drop the floors and ceilings 1 if n 1 T n 2T n 2 n otherwise Suppose that we draw the recursion tree for MergeSort but each time we merge two lists we label that node of the tree with the time it takes to perform the associated nonrecursive merge Recall that to merge two lists of size m 2 to a list of size m takes m time which we will just write as m Below is an illustration of the resulting recursion tree T n n T n 2 n 2 T n 4 n 4 n T n 2 n 2 n 4 n 4 n 4 1 1 1 1 2 n 2 n 4 n 4 n n n n n lg n 1 levels n lg n 1 Figure 5 Using the recursion tree to visualize a recurrence Observe that the total work at the topmost level of the recursion is n or just n for short At the second level we have two merges each taking n 2 time for a total of 2 n 2 n At the third level we have 4 merges each taking n 4 time for a total of 4 n 4 n This continues until the bottommost level of the tree Since the tree exactly lg n 1 levels 0 1 2 lg n and each level contributes a total of n time the total running time is n lg n 1 n lg n n This is exactly what we got by the iteration method This can be used for a number of simple recurrences For example let s try it on the following recurrence The tree is illustrated below 1 if n 1 T n otherwise 3T n 2 n2 Again we label each node with the amount of work at that level In this case the work for T m is m2 For the top level or 0th level the work is n2 At level 1 we have three nodes whose work is n 2 2 each for a total of 3 n 2 2 This can be written as n2 3 4 At the level 2 the work is 9 n 4 2 which can be written as n2 9 16 In general it is easy to extrapolate to see that at the level i we have 3i nodes each involving n 2i 2 work for a total of 3i n 2i 2 n2 3 4 i This leads to the following summation Note that we have not determined where the tree bottoms out so we have left off the upper bound on the sum i X 3 2 T n n 4 i 0 28 Lecture Notes CMSC 251 T n n2 T n 2 n 2 2 T n 2 n 2 2 T n 2 n 2 2 T n 4 n 4 2 n 4 2 n 4 2 n 4 2 n 4 2 n 4 2 n2 3 n 2 2 n2 3 4 2 9 n 4 n2 9 16 n 2 3 4 i Figure 6 Another recursion tree example If all we wanted was an asymptotic expression then are essentially done at this point Why The summation is a geometric series and the base 3 4 is less than 1 This means that this series converges to some nonzero constant even if we ran the sum out to Thus the running time is n2 To get a more exact result observe that the recursion bottoms out when we get down to single items and since the sizes of the inputs are cut by half at each level it is not hard to see that the final level is level lg n It is easy to be off by 1 here but this sort of small error will not affect the asymptotic result In this case we happen to be right So we can plug in lg n for the in the above summation T n n2 lg n i X 3 i 0 4 If we wanted to get a more …