text:
标 签:Algorithms
Introduction to Algorithms 3rd
0, be a degree-d polynomial in n, and let k be a constant. Use the definitions of the asymptotic notations to prove the following properties. a. If k d , then p.n/ D O.nk/. b. If k Ä d , then p.n/ D .nk/. c. If k D d , then p.n/ D '.nk/. d. If k > d , then p.n/ D o.nk/. e. If k < d , then p.n/ D !.nk/. 3-2 Relative asymptotic growths Indicate, for each pair of expressions .A; B/ in the table below, whether A is O, o, , !, or ' of B. Assume that k 1, > 0, and c > 1 are constants. Your answer should be in the form of the table with "yes" or "no" written in each box. A B Oo a. lgk n n b. nk p c. n cn nsin n d. 2n 2n=2 e. nlg c clg n f. lg.nŠ/ lg.nn/ ! ' 3-3 Ordering by asymptotic growth rates a. Rank the following functions by order of growth; that is, find an arrangement g1; g2; : : : ; g30 of the functions satisfying g1 D .g2/, g2 D .g3/, . . . , g29 D .g30/. Partition your list into equivalence classes such that functions f .n/ and g.n/ are in the same class if and only if f .n/ D '.g.n//. 62 Chapter 3 Growth of Functions lg.lg n/ . 3 2 /n ln ln n 2lg n lg .lg n/ 2lg n n3 lg n .lg n/lg n p 2 2 lg n p . 2/lg n lg2 n n 2n en n n2 lg.nŠ/ nlg lg n 4lg n 2n nŠ 22n ln n .n C 1/Š n lg n .lg n/Š n1= lg n 1 p lg n 22nC1 b. Give an example of a single nonnegative function f .n/ such that for all functions gi .n/ in part (a), f .n/ is neither O.gi .n// nor .gi .n//. 3-4 Asymptotic notation properties Let f .n/ and g.n/ be asymptotically positive functions. Prove or disprove each of the following conjectures. a. f .n/ D O.g.n// implies g.n/ D O.f .n//. b. f .n/ C g.n/ D '.min.f .n/; g.n///. c. f .n/ D O.g.n// implies lg.f .n// D O.lg.g.n///, where lg.g.n// 1 and f .n/ 1 for all sufficiently large n. d. f .n/ D O.g.n// implies 2f .n/ D O 2g.n/ . e. f .n/ D O ..f .n//2/. f. f .n/ D O.g.n// implies g.n/ D .f .n//. g. f .n/ D '.f .n=2//. h. f .n/ C o.f .n// D '.f .n//. 3-5 Variations on O and ˝ 1 Some authors define in a slightly different way than we do; let's use (read 1 "omega infinity") for this alternative definition. We say that f .n/ D .g.n// if there exists a positive constant c such that f .n/ cg.n/ 0 for infinitely many integers n. a. Show that for any two functions f .n/ and g.n/ that are asymptotically nonneg1 ative, either f .n/ D O.g.n// or f .n/ D .g.n// or both, whereas this is not 1 true if we use in place of . Problems for Chapter 3 63 1 b. Describe the potential advantages and disadvantages of using instead of to characterize the running times of programs. Some authors also define O in a slightly different manner; let's use O0 for the alternative definition. We say that f .n/ D O0.g.n// if and only if jf .n/j D O.g.n//. c. What happens to each direction of the "if and only if" in Theorem 3.1 if we substitute O0 for O but still use ? Some authors define Oe (read "soft-oh") to mean O with logarithmic factors ignored: Oe.g.n// D ff .n/ W there exist positive constants c, k, and n0 such that 0 Ä f .n/ Ä cg.n/ lgk.n/ for all n n0g : d. Define e and 'e in a similar manner. Prove the corresponding analog to Theorem 3.1. 3-6 Iterated functions We can apply the iteration operator used in the lg function to any monotonically increasing function f .n/ over the reals. For a given constant c 2 R, we define the iterated function fc by ˚ fc .n/ D min i 0 W f .i /.n/ Ä « c ; which need not be well defined in all cases. In other words, the quantity fc .n/ is the number of iterated applications of the function f required to reduce its argument down to c or less. For each of the following functions f .n/ and constants c, give as tight a bound as possible on fc .n/. f .n/ c a. n 1 0 fc .n/ b. lg n 1 c. n=2 1 d. n=2 2 p e. n 2 p f. n 1 g. n1=3 2 h. n= lg n 2 64 Chapter 3 Growth of Functions Chapter notes Knuth [209] traces the origin of the O-notation to a number-theory text by P. Bachmann in 1892. The o-notation was invented by E. Landau in 1909 for his discussion of the distribution of prime numbers. The and ' notations were advocated by Knuth [213] to correct the popular, but technically sloppy, practice in the literature of using O-notation for both upper and lower bounds. Many people continue to use the O-notation where the '-notation is more technically precise. Further discussion of the history and development of asymptotic notations appears in works by Knuth [209, 213] and Brassard and Bratley [54]. Not all authors define the asymptotic notations in the same way, although the various definitions agree in most common situations. Some of the alternative definitions encompass functions that are not asymptotically nonnegative, as long as their absolute values are appropriately bounded. Equation (3.20) is due to Robbins [297]. Other properties of elementary mathematical functions can be found in any good mathematical reference, such as Abramowitz and Stegun [1] or Zwillinger [362], or in a calculus book, such as Apostol [18] or Thomas et al. [334]. Knuth [209] and Graham, Knuth, and Patashnik [152] contain a wealth of material on discrete mathematics as used in computer science. 4 Divide-and-Conquer In Section 2.3.1, we saw how merge sort serves as an example of the divide-andconquer paradigm. Recall that in divide-and-conquer, we solve a problem recursively, applying three steps at each level of the recursion: Divide the problem into a number of subproblems that are smaller instances of the same problem. Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner. Combine the solutions to the subproblems into the solution for the original problem. When the subproblems are large enough to solve recursively, we call that the recursive case. Once the subproblems become small enough that we no longer recurse, we say that the recursion "bottoms out" and that we have gotten down to the base case. Sometimes, in addition to subproblems that are smaller instances of the same problem, we have to solve subproblems that are not quite the same as the original problem. We consider solving such subproblems as part of the combine step. In this chapter, we shall see more algorithms based on divide-and-conquer. The first one solves the maximum-subarray problem: it takes as input an array of numbers, and it determines the contiguous subarray whose values have the greatest sum. Then we shall see two divide-and-conquer algorithms for multiplying n n matrices. One runs in '.n3/ time, which is no better than the straightforward method of multiplying square matrices. But the other, Strassen's algorithm, runs in O.n2:81/ time, which beats the straightforward method asymptotically. Recurrences Recurrences go hand in hand with the divide-and-conquer paradigm, because they give us a natural way to characterize the running times of divide-and-conquer algorithms. A recurrence is an equation or inequality that describes a function in terms 66 Chapter 4 Divide-and-Conquer of its value on smaller inputs. For example, in Section 2.3.2 we described the worst-case running time T .n/ of the MERGE-SORT procedure by the recurrence ( T .n/ D '.1/ if n D 1 ; (4.1) 2T .n=2/ C '.n/ if n > 1 ; whose solution we claimed to be T .n/ D '.n lg n/. Recurrences can take many forms. For example, a recursive algorithm might divide subproblems into unequal sizes, such as a 2=3-to-1=3 split. If the divide and combine steps take linear time, such an algorithm would give rise to the recurrence T .n/ D T .2n=3/ C T .n=3/ C '.n/. Subproblems are not necessarily constrained to being a constant fraction of the original problem size. For example, a recursive version of linear search (see Exercise 2.1-3) would create just one subproblem containing only one element fewer than the original problem. Each recursive call would take constant time plus the time for the recursive calls it makes, yielding the recurrence T .n/ D T .n 1/ C '.1/. This chapter offers three methods for solving recurrences—that is, for obtaining asymptotic "'" or "O" bounds on the solution: In the substitution method, we guess a bound and then use mathematical induction to prove our guess correct. The recursion-tree method converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion. We use techniques for bounding summations to solve the recurrence. The master method provides bounds for recurrences of the form T .n/ D aT .n=b/ C f .n/ ; (4.2) where a 1, b > 1, and f .n/ is a given function. Such recurrences arise frequently. A recurrence of the form in equation (4.2) characterizes a divideand-conquer algorithm that creates a subproblems, each of which is 1=b the size of the original problem, and in which the divide and combine steps together take f .n/ time. To use the master method, you will need to memorize three cases, but once you do that, you will easily be able to determine asymptotic bounds for many simple recurrences. We will use the master method to determine the running times of the divide-and-conquer algorithms for the maximum-subarray problem and for matrix multiplication, as well as for other algorithms based on divideand-conquer elsewhere in this book. Chapter 4 Divide-and-Conquer 67 Occasionally, we shall see recurrences that are not equalities but rather inequalities, such as T .n/ Ä 2T .n=2/ C '.n/. Because such a recurrence states only an upper bound on T .n/, we will couch its solution using O-notation rather than '-notation. Similarly, if the inequality were reversed to T .n/ 2T .n=2/ C '.n/, then because the recurrence gives only a lower bound on T .n/, we would use -notation in its solution. Technicalities in recurrences In practice, we neglect certain technical details when we state and solve recur- rences. For example, if we call MERGE-SORT on n elements when n is odd, we end up with subproblems of size bn=2c and dn=2e. Neither size is actually n=2, because n=2 is not an integer when n is odd. Technically, the recurrence describing the worst-case running time of MERGE-SORT is really ( T .n/ D '.1/ if n D 1 ; (4.3) T .dn=2e/ C T .bn=2c/ C '.n/ if n > 1 : Boundary conditions represent another class of details that we typically ignore. Since the running time of an algorithm on a constant-sized input is a constant, the recurrences that arise from the running times of algorithms generally have T .n/ D '.1/ for sufficiently small n. Consequently, for convenience, we shall generally omit statements of the boundary conditions of recurrences and assume that T .n/ is constant for small n. For example, we normally state recurrence (4.1) as T .n/ D 2T .n=2/ C '.n/ ; (4.4) without explicitly giving values for small n. The reason is that although changing the value of T .1/ changes the exact solution to the recurrence, the solution typically doesn't change by more than a constant factor, and so the order of growth is unchanged. When we state and solve recurrences, we often omit floors, ceilings, and boundary conditions. We forge ahead without these details and later determine whether or not they matter. They usually do not, but you should know when they do. Experience helps, and so do some theorems stating that these details do not affect the asymptotic bounds of many recurrences characterizing divide-and-conquer algorithms (see Theorem 4.1). In this chapter, however, we shall address some of these details and illustrate the fine points of recurrence solution methods. 68 Chapter 4 Divide-and-Conquer 4.1 The maximum-subarray problem Suppose that you been offered the opportunity to invest in the Volatile Chemical Corporation. Like the chemicals the company produces, the stock price of the Volatile Chemical Corporation is rather volatile. You are allowed to buy one unit of stock only one time and then sell it at a later date, buying and selling after the close of trading for the day. To compensate for this restriction, you are allowed to learn what the price of the stock will be in the future. Your goal is to maximize your profit. Figure 4.1 shows the price of the stock over a 17-day period. You may buy the stock at any one time, starting after day 0, when the price is $100 per share. Of course, you would want to "buy low, sell high"—buy at the lowest possible price and later on sell at the highest possible price—to maximize your profit. Unfortunately, you might not be able to buy at the lowest price and then sell at the highest price within a given period. In Figure 4.1, the lowest price occurs after day 7, which occurs after the highest price, after day 1. You might think that you can always maximize profit by either buying at the lowest price or selling at the highest price. For example, in Figure 4.1, we would maximize profit by buying at the lowest price, after day 7. If this strategy always worked, then it would be easy to determine how to maximize profit: find the highest and lowest prices, and then work left from the highest price to find the lowest prior price, work right from the lowest price to find the highest later price, and take the pair with the greater difference. Figure 4.2 shows a simple counterexample, 120 110 100 90 80 70 60 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Day 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Price 100 113 110 85 105 102 86 63 81 101 94 106 101 79 94 90 97 Change 13 3 25 20 3 16 23 18 20 7 12 5 22 15 4 7 Figure 4.1 Information about the price of stock in the Volatile Chemical Corporation after the close of trading over a period of 17 days. The horizontal axis of the chart indicates the day, and the vertical axis shows the price. The bottom row of the table gives the change in price from the previous day. 4.1 The maximum-subarray problem 69 11 10 9 8 7 6 01234 Day 01 23 4 Price 10 11 7 10 6 Change 1 43 4 Figure 4.2 An example showing that the maximum profit does not always start at the lowest price or end at the highest price. Again, the horizontal axis indicates the day, and the vertical axis shows the price. Here, the maximum profit of $3 per share would be earned by buying after day 2 and selling after day 3. The price of $7 after day 2 is not the lowest price overall, and the price of $10 after day 3 is not the highest price overall. demonstrating that the maximum profit sometimes comes neither by buying at the lowest price nor by selling at the highest price. A brute-force solution We can easily devise a brute-force solution to this problem: just try every possible pair of buy and sell dates in which the buy date precedes the sell date. A period of n days has n 2 such pairs of dates. Since n 2 is '.n2/, and the best we can hope for is to evaluate each pair of dates in constant time, this approach would take .n2/ time. Can we do better? A transformation In order to design an algorithm with an o.n2/ running time, we will look at the input in a slightly different way. We want to find a sequence of days over which the net change from the first day to the last is maximum. Instead of looking at the daily prices, let us instead consider the daily change in price, where the change on day i is the difference between the prices after day i 1 and after day i. The table in Figure 4.1 shows these daily changes in the bottom row. If we treat this row as an array A, shown in Figure 4.3, we now want to find the nonempty, contiguous subarray of A whose values have the largest sum. We call this contiguous subarray the maximum subarray. For example, in the array of Figure 4.3, the maximum subarray of AŒ1 : : 16 is AŒ8 : : 11, with the sum 43. Thus, you would want to buy the stock just before day 8 (that is, after day 7) and sell it after day 11, earning a profit of $43 per share. At first glance, this transformation does not help. We still need to check n1 2 D '.n2/ subarrays for a period of n days. Exercise 4.1-2 asks you to show 70 Chapter 4 Divide-and-Conquer 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 A 13 –3 –25 20 –3 –16 –23 18 20 –7 12 –5 –22 15 –4 7 maximum subarray Figure 4.3 The change in stock prices as a maximum-subarray problem. Here, the subarray AŒ8 : : 11, with sum 43, has the greatest sum of any contiguous subarray of array A. that although computing the cost of one subarray might take time proportional to the length of the subarray, when computing all '.n2/ subarray sums, we can organize the computation so that each subarray sum takes O.1/ time, given the values of previously computed subarray sums, so that the brute-force solution takes '.n2/ time. So let us seek a more efficient solution to the maximum-subarray problem. When doing so, we will usually speak of "a" maximum subarray rather than "the" maximum subarray, since there could be more than one subarray that achieves the maximum sum. The maximum-subarray problem is interesting only when the array contains some negative numbers. If all the array entries were nonnegative, then the maximum-subarray problem would present no challenge, since the entire array would give the greatest sum. A solution using divide-and-conquer Let's think about how we might solve the maximum-subarray problem using the divide-and-conquer technique. Suppose we want to find a maximum subarray of the subarray AŒlow : : high. Divide-and-conquer suggests that we divide the subarray into two subarrays of as equal size as possible. That is, we find the midpoint, say mid, of the subarray, and consider the subarrays AŒlow : : mid and AŒmid C 1 : : high. As Figure 4.4(a) shows, any contiguous subarray AŒi : : j of AŒlow : : high must lie in exactly one of the following places: entirely in the subarray AŒlow : : mid, so that low Ä i Ä j Ä mid, entirely in the subarray AŒmid C 1 : : high, so that mid < i Ä j Ä high, or crossing the midpoint, so that low Ä i Ä mid < j Ä high. Therefore, a maximum subarray of AŒlow : : high must lie in exactly one of these places. In fact, a maximum subarray of AŒlow : : high must have the greatest sum over all subarrays entirely in AŒlow : : mid, entirely in AŒmid C 1 : : high, or crossing the midpoint. We can find maximum subarrays of AŒlow : : mid and AŒmidC1 : : high recursively, because these two subproblems are smaller instances of the problem of finding a maximum subarray. Thus, all that is left to do is find a 4.1 The maximum-subarray problem 71 crosses the midpoint low mid high low AŒmid C 1 : : j i mid high mid C 1 entirely in AŒlow : : mid entirely in AŒmid C 1 : : high (a) mid C 1 j AŒi : : mid (b) Figure 4.4 (a) Possible locations of subarrays of AŒlow : : high: entirely in AŒlow : : mid, entirely in AŒmid C 1 : : high, or crossing the midpoint mid. (b) Any subarray of AŒlow : : high crossing the midpoint comprises two subarrays AŒi : : mid and AŒmid C 1 : : j , where low Ä i Ä mid and mid < j Ä high. maximum subarray that crosses the midpoint, and take a subarray with the largest sum of the three. We can easily find a maximum subarray crossing the midpoint in time linear in the size of the subarray AŒlow : : high. This problem is not a smaller instance of our original problem, because it has the added restriction that the subarray it chooses must cross the midpoint. As Figure 4.4(b) shows, any subarray crossing the midpoint is itself made of two subarrays AŒi : : mid and AŒmid C 1 : : j , where low Ä i Ä mid and mid < j Ä high. Therefore, we just need to find maximum subarrays of the form AŒi : : mid and AŒmid C 1 : : j and then combine them. The procedure FIND-MAX-CROSSING-SUBARRAY takes as input the array A and the indices low, mid, and high, and it returns a tuple containing the indices demarcating a maximum subarray that crosses the midpoint, along with the sum of the values in a maximum subarray. FIND-MAX-CROSSING-SUBARRAY.A; low; mid; high/ 1 left-sum D 1 2 sum D 0 3 for i D mid downto low 4 sum D sum C AŒi 5 if sum > left-sum 6 left-sum D sum 7 max-left D i 8 right-sum D 1 9 sum D 0 10 for j D mid C 1 to high 11 sum D sum C AŒj 12 if sum > right-sum 13 right-sum D sum 14 max-right D j 15 return .max-left; max-right; left-sum C right-sum/ 72 Chapter 4 Divide-and-Conquer This procedure works as follows. Lines 1–7 find a maximum subarray of the left half, AŒlow : : mid. Since this subarray must contain AŒmid, the for loop of lines 3–7 starts the index i at mid and works down to low, so that every subarray it considers is of the form AŒi : : mid. Lines 1–2 initialize the variables left-sum, which holds the greatest sum found so far, and sum, holding the sum of the entries in AŒi : : mid. Whenever we find, in line 5, a subarray AŒi : : mid with a sum of values greater than left-sum, we update left-sum to this subarray's sum in line 6, and in line 7 we update the variable max-left to record this index i. Lines 8–14 work analogously for the right half, AŒmid C 1 : : high. Here, the for loop of lines 10–14 starts the index j at midC1 and works up to high, so that every subarray it considers is of the form AŒmid C 1 : : j . Finally, line 15 returns the indices max-left and max-right that demarcate a maximum subarray crossing the midpoint, along with the sum left-sum Cright-sum of the values in the subarray AŒmax-left : : max-right. If the subarray AŒlow : : high contains n entries (so that n D high low C 1), we claim that the call FIND-MAX-CROSSING-SUBARRAY.A; low; mid; high/ takes '.n/ time. Since each iteration of each of the two for loops takes '.1/ time, we just need to count up how many iterations there are altogether. The for loop of lines 3–7 makes mid low C 1 iterations, and the for loop of lines 10–14 makes high mid iterations, and so the total number of iterations is .mid low C 1/ C .high mid/ D high low C 1 D n: With a linear-time FIND-MAX-CROSSING-SUBARRAY procedure in hand, we can write pseudocode for a divide-and-conquer algorithm to solve the maximumsubarray problem: FIND-MAXIMUM-SUBARRAY.A; low; high/ 1 if high == low 2 return .low; high; AŒlow/ // base case: only one element 3 else mid D b.low C high/=2c 4 .left-low; left-high; left-sum/ D FIND-MAXIMUM-SUBARRAY.A; low; mid/ 5 .right-low; right-high; right-sum/ D FIND-MAXIMUM-SUBARRAY.A; mid C 1; high/ 6 .cross-low; cross-high; cross-sum/ D FIND-MAX-CROSSING-SUBARRAY .A; low; mid; high/ 7 if left-sum right-sum and left-sum cross-sum 8 return .left-low; left-high; left-sum/ 9 elseif right-sum left-sum and right-sum cross-sum 10 return .right-low; right-high; right-sum/ 11 else return .cross-low; cross-high; cross-sum/ 4.1 The maximum-subarray problem 73 The initial call FIND-MAXIMUM-SUBARRAY.A; 1; A:length/ will find a maximum subarray of AŒ1 : : n. Similar to FIND-MAX-CROSSING-SUBARRAY, the recursive procedure FINDMAXIMUM-SUBARRAY returns a tuple containing the indices that demarcate a maximum subarray, along with the sum of the values in a maximum subarray. Line 1 tests for the base case, where the subarray has just one element. A subarray with just one element has only one subarray—itself—and so line 2 returns a tuple with the starting and ending indices of just the one element, along with its value. Lines 3–11 handle the recursive case. Line 3 does the divide part, computing the index mid of the midpoint. Let's refer to the subarray AŒlow : : mid as the left subarray and to AŒmid C 1 : : high as the right subarray. Because we know that the subarray AŒlow : : high contains at least two elements, each of the left and right subarrays must have at least one element. Lines 4 and 5 conquer by recursively finding maximum subarrays within the left and right subarrays, respectively. Lines 6–11 form the combine part. Line 6 finds a maximum subarray that crosses the midpoint. (Recall that because line 6 solves a subproblem that is not a smaller instance of the original problem, we consider it to be in the combine part.) Line 7 tests whether the left subarray contains a subarray with the maximum sum, and line 8 returns that maximum subarray. Otherwise, line 9 tests whether the right subarray contains a subarray with the maximum sum, and line 10 returns that maximum subarray. If neither the left nor right subarrays contain a subarray achieving the maximum sum, then a maximum subarray must cross the midpoint, and line 11 returns it. Analyzing the divide-and-conquer algorithm Next we set up a recurrence that describes the running time of the recursive FINDMAXIMUM-SUBARRAY procedure. As we did when we analyzed merge sort in Section 2.3.2, we make the simplifying assumption that the original problem size is a power of 2, so that all subproblem sizes are integers. We denote by T .n/ the running time of FIND-MAXIMUM-SUBARRAY on a subarray of n elements. For starters, line 1 takes constant time. The base case, when n D 1, is easy: line 2 takes constant time, and so T .1/ D '.1/ : (4.5) The recursive case occurs when n > 1. Lines 1 and 3 take constant time. Each of the subproblems solved in lines 4 and 5 is on a subarray of n=2 elements (our assumption that the original problem size is a power of 2 ensures that n=2 is an integer), and so we spend T .n=2/ time solving each of them. Because we have to solve two subproblems—for the left subarray and for the right subarray—the contribution to the running time from lines 4 and 5 comes to 2T .n=2/. As we have 74 Chapter 4 Divide-and-Conquer already seen, the call to FIND-MAX-CROSSING-SUBARRAY in line 6 takes '.n/ time. Lines 7–11 take only '.1/ time. For the recursive case, therefore, we have T .n/ D '.1/ C 2T .n=2/ C '.n/ C '.1/ D 2T .n=2/ C '.n/ : (4.6) Combining equations (4.5) and (4.6) gives us a recurrence for the running time T .n/ of FIND-MAXIMUM-SUBARRAY: ( T .n/ D '.1/ if n D 1 ; 2T .n=2/ C '.n/ if n > 1 : (4.7) This recurrence is the same as recurrence (4.1) for merge sort. As we shall see from the master method in Section 4.5, this recurrence has the solution T .n/ D '.n lg n/. You might also revisit the recursion tree in Figure 2.5 to understand why the solution should be T .n/ D '.n lg n/. Thus, we see that the divide-and-conquer method yields an algorithm that is asymptotically faster than the brute-force method. With merge sort and now the maximum-subarray problem, we begin to get an idea of how powerful the divideand-conquer method can be. Sometimes it will yield the asymptotically fastest algorithm for a problem, and other times we can do even better. As Exercise 4.1-5 shows, there is in fact a linear-time algorithm for the maximum-subarray problem, and it does not use divide-and-conquer. Exercises 4.1-1 What does FIND-MAXIMUM-SUBARRAY return when all elements of A are negative? 4.1-2 Write pseudocode for the brute-force method of solving the maximum-subarray problem. Your procedure should run in '.n2/ time. 4.1-3 Implement both the brute-force and recursive algorithms for the maximumsubarray problem on your own computer. What problem size n0 gives the crossover point at which the recursive algorithm beats the brute-force algorithm? Then, change the base case of the recursive algorithm to use the brute-force algorithm whenever the problem size is less than n0. Does that change the crossover point? 4.1-4 Suppose we change the definition of the maximum-subarray problem to allow the result to be an empty subarray, where the sum of the values of an empty subar- 4.2 Strassen's algorithm for matrix multiplication 75 ray is 0. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result? 4.1-5 Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximum-subarray problem. Start at the left end of the array, and progress toward the right, keeping track of the maximum subarray seen so far. Knowing a maximum subarray of AŒ1 : : j , extend the answer to find a maximum subarray ending at index j C1 by using the following observation: a maximum subarray of AŒ1 : : j C 1 is either a maximum subarray of AŒ1 : : j or a subarray AŒi : : j C 1, for some 1 Ä i Ä j C 1. Determine a maximum subarray of the form AŒi : : j C 1 in constant time based on knowing a maximum subarray ending at index j . 4.2 Strassen's algorithm for matrix multiplication If you have seen matrices before, then you probably know how to multiply them. (Otherwise, you should read Section D.1 in Appendix D.) If A D .aij / and B D .bij / are square n n matrices, then in the product C D A B, we define the entry cij , for i; j D 1; 2; : : : ; n, by Xn cij D aik bkj : kD1 (4.8) We must compute n2 matrix entries, and each is the sum of n values. The following procedure takes n n matrices A and B and multiplies them, returning their n n product C . We assume that each matrix has an attribute rows, giving the number of rows in the matrix. SQUARE-MATRIX-MULTIPLY.A; B/ 1 n D A:rows 2 let C be a new n n matrix 3 for i D 1 to n 4 for j D 1 to n 5 cij D 0 6 for k D 1 to n 7 cij D cij C aik bkj 8 return C The SQUARE-MATRIX-MULTIPLY procedure works as follows. The for loop of lines 3–7 computes the entries of each row i, and within a given row i, the 76 Chapter 4 Divide-and-Conquer for loop of lines 4–7 computes each of the entries cij , for each column j . Line 5 initializes cij to 0 as we start computing the sum given in equation (4.8), and each iteration of the for loop of lines 6–7 adds in one more term of equation (4.8). Because each of the triply-nested for loops runs exactly n iterations, and each execution of line 7 takes constant time, the SQUARE-MATRIX-MULTIPLY procedure takes '.n3/ time. You might at first think that any matrix multiplication algorithm must take .n3/ time, since the natural definition of matrix multiplication requires that many mul- tiplications. You would be incorrect, however: we have a way to multiply matrices in o.n3/ time. In this section, we shall see Strassen's remarkable recursive algorithm for multiplying n n matrices. It runs in '.nlg 7/ time, which we shall show in Section 4.5. Since lg 7 lies between 2:80 and 2:81, Strassen's algorithm runs in O.n2:81/ time, which is asymptotically better than the simple SQUARE-MATRIX- MULTIPLY procedure. A simple divide-and-conquer algorithm To keep things simple, when we use a divide-and-conquer algorithm to compute the matrix product C D A B, we assume that n is an exact power of 2 in each of the n n matrices. We make this assumption because in each divide step, we will divide n n matrices into four n=2 n=2 matrices, and by assuming that n is an exact power of 2, we are guaranteed that as long as n 2, the dimension n=2 is an integer. Suppose that we partition each of A, B, and C into four n=2 n=2 matrices  à AD A11 A12 A21 A22 ;  à BD B11 B12 B21 B22 ;  à CD C11 C12 C21 C22 ; (4.9) so that we rewrite the equation C D A B as  C11 C21 àC12 C22 D A11 A21 àA12 B11 A22 B21 à B12 B22 : (4.10) Equation (4.10) corresponds to the four equations C11 D A11 B11 C A12 B21 ; C12 D A11 B12 C A12 B22 ; C21 D A21 B11 C A22 B21 ; C22 D A21 B12 C A22 B22 : (4.11) (4.12) (4.13) (4.14) Each of these four equations specifies two multiplications of n=2 n=2 matrices and the addition of their n=2 n=2 products. We can use these equations to create a straightforward, recursive, divide-and-conquer algorithm: 4.2 Strassen's algorithm for matrix multiplication 77 SQUARE-MATRIX-MULTIPLY-RECURSIVE .A; B/ 1 n D A:rows 2 let C be a new n n matrix 3 if n == 1 4 c11 D a11 b11 5 else partition A, B, and C as in equations (4.9) 6 C11 D SQUARE-MATRIX-MULTIPLY-RECURSIVE .A11; B11/ C SQUARE-MATRIX-MULTIPLY-RECURSIVE.A12; B21/ 7 C12 D SQUARE-MATRIX-MULTIPLY-RECURSIVE .A11; B12/ C SQUARE-MATRIX-MULTIPLY-RECURSIVE.A12; B22/ 8 C21 D SQUARE-MATRIX-MULTIPLY-RECURSIVE .A21; B11/ C SQUARE-MATRIX-MULTIPLY-RECURSIVE.A22; B21/ 9 C22 D SQUARE-MATRIX-MULTIPLY-RECURSIVE .A21; B12/ C SQUARE-MATRIX-MULTIPLY-RECURSIVE.A22; B22/ 10 return C This pseudocode glosses over one subtle but important implementation detail. How do we partition the matrices in line 5? If we were to create 12 new n=2 n=2 matrices, we would spend '.n2/ time copying entries. In fact, we can partition the matrices without copying entries. The trick is to use index calculations. We identify a submatrix by a range of row indices and a range of column indices of the original matrix. We end up representing a submatrix a little differently from how we represent the original matrix, which is the subtlety we are glossing over. The advantage is that, since we can specify submatrices by index calculations, executing line 5 takes only '.1/ time (although we shall see that it makes no difference asymptotically to the overall running time whether we copy or partition in place). Now, we derive a recurrence to characterize the running time of SQUAREMATRIX-MULTIPLY-RECURSIVE. Let T .n/ be the time to multiply two n n matrices using this procedure. In the base case, when n D 1, we perform just the one scalar multiplication in line 4, and so T .1/ D '.1/ : (4.15) The recursive case occurs when n > 1. As discussed, partitioning the matrices in line 5 takes '.1/ time, using index calculations. In lines 6–9, we recursively call SQUARE-MATRIX-MULTIPLY-RECURSIVE a total of eight times. Because each recursive call multiplies two n=2 n=2 matrices, thereby contributing T .n=2/ to the overall running time, the time taken by all eight recursive calls is 8T .n=2/. We also must account for the four matrix additions in lines 6–9. Each of these matrices contains n2=4 entries, and so each of the four matrix additions takes '.n2/ time. Since the number of matrix additions is a constant, the total time spent adding ma- 78 Chapter 4 Divide-and-Conquer trices in lines 6–9 is '.n2/. (Again, we use index calculations to place the results of the matrix additions into the correct positions of matrix C , with an overhead of '.1/ time per entry.) The total time for the recursive case, therefore, is the sum of the partitioning time, the time for all the recursive calls, and the time to add the matrices resulting from the recursive calls: T .n/ D '.1/ C 8T .n=2/ C '.n2/ D 8T .n=2/ C '.n2/ : (4.16) Notice that if we implemented partitioning by copying matrices, which would cost '.n2/ time, the recurrence would not change, and hence the overall running time would increase by only a constant factor. Combining equations (4.15) and (4.16) gives us the recurrence for the running time of SQUARE-MATRIX-MULTIPLY-RECURSIVE: ( '.1/ if n D 1 ; T .n/ D 8T .n=2/ C '.n2/ if n > 1 : (4.17) As we shall see from the master method in Section 4.5, recurrence (4.17) has the solution T .n/ D '.n3/. Thus, this simple divide-and-conquer approach is no faster than the straightforward SQUARE-MATRIX-MULTIPLY procedure. Before we continue on to examining Strassen's algorithm, let us review where the components of equation (4.16) came from. Partitioning each n n matrix by index calculation takes '.1/ time, but we have two matrices to partition. Although you could say that partitioning the two matrices takes '.2/ time, the constant of 2 is subsumed by the '-notation. Adding two matrices, each with, say, k entries, takes '.k/ time. Since the matrices we add each have n2=4 entries, you could say that adding each pair takes '.n2=4/ time. Again, however, the '-notation subsumes the constant factor of 1=4, and we say that adding two n2=4 n2=4 matrices takes '.n2/ time. We have four such matrix additions, and once again, instead of saying that they take '.4n2/ time, we say that they take '.n2/ time. (Of course, you might observe that we could say that the four matrix additions take '.4n2=4/ time, and that 4n2=4 D n2, but the point here is that '-notation subsumes constant factors, whatever they are.) Thus, we end up with two terms of '.n2/, which we can combine into one. When we account for the eight recursive calls, however, we cannot just subsume the constant factor of 8. In other words, we must say that together they take 8T .n=2/ time, rather than just T .n=2/ time. You can get a feel for why by looking back at the recursion tree in Figure 2.5, for recurrence (2.1) (which is identical to recurrence (4.7)), with the recursive case T .n/ D 2T .n=2/C'.n/. The factor of 2 determined how many children each tree node had, which in turn determined how many terms contributed to the sum at each level of the tree. If we were to ignore 4.2 Strassen's algorithm for matrix multiplication 79 the factor of 8 in equation (4.16) or the factor of 2 in recurrence (4.1), the recursion tree would just be linear, rather than "bushy," and each level would contribute only one term to the sum. Bear in mind, therefore, that although asymptotic notation subsumes constant multiplicative factors, recursive notation such as T .n=2/ does not. Strassen's method The key to Strassen's method is to make the recursion tree slightly less bushy. That is, instead of performing eight recursive multiplications of n=2 n=2 matrices, it performs only seven. The cost of eliminating one matrix multiplication will be several new additions of n=2 n=2 matrices, but still only a constant number of additions. As before, the constant number of matrix additions will be subsumed by '-notation when we set up the recurrence equation to characterize the running time. Strassen's method is not at all obvious. (This might be the biggest understatement in this book.) It has four steps: 1. Divide the input matrices A and B and output matrix C into n=2 n=2 submatrices, as in equation (4.9). This step takes '.1/ time by index calculation, just as in SQUARE-MATRIX-MULTIPLY-RECURSIVE. 2. Create 10 matrices S1; S2; : : : ; S10, each of which is n=2 n=2 and is the sum or difference of two matrices created in step 1. We can create all 10 matrices in '.n2/ time. 3. Using the submatrices created in step 1 and the 10 matrices created in step 2, recursively compute seven matrix products P1; P2; : : : ; P7. Each matrix Pi is n=2 n=2. 4. Compute the desired submatrices C11; C12; C21; C22 of the result matrix C by adding and subtracting various combinations of the Pi matrices. We can compute all four submatrices in '.n2/ time. We shall see the details of steps 2–4 in a moment, but we already have enough information to set up a recurrence for the running time of Strassen's method. Let us assume that once the matrix size n gets down to 1, we perform a simple scalar mul- tiplication, just as in line 4 of SQUARE-MATRIX-MULTIPLY-RECURSIVE. When n > 1, steps 1, 2, and 4 take a total of '.n2/ time, and step 3 requires us to per- form seven multiplications of n=2 n=2 matrices. Hence, we obtain the following recurrence for the running time T .n/ of Strassen's algorithm: ( T .n/ D '.1/ 7T .n=2/ C '.n2/ if n D 1 ; if n > 1 : (4.18) 80 Chapter 4 Divide-and-Conquer We have traded off one matrix multiplication for a constant number of matrix additions. Once we understand recurrences and their solutions, we shall see that this tradeoff actually leads to a lower asymptotic running time. By the master method in Section 4.5, recurrence (4.18) has the solution T .n/ D '.nlg 7/. We now proceed to describe the details. In step 2, we create the following 10 matrices: S1 D B12 B22 ; S2 D A11 C A12 ; S3 D A21 C A22 ; S4 D B21 B11 ; S5 D A11 C A22 ; S6 D B11 C B22 ; S7 D A12 A22 ; S8 D B21 C B22 ; S9 D A11 A21 ; S10 D B11 C B12 : Since we must add or subtract n=2 n=2 matrices 10 times, this step does indeed take '.n2/ time. In step 3, we recursively multiply n=2 n=2 matrices seven times to compute the following n=2 n=2 matrices, each of which is the sum or difference of products of A and B submatrices: P1 D A11 S1 D A11 B12 A11 B22 ; P2 D S2 B22 D A11 B22 C A12 B22 ; P3 D S3 B11 D A21 B11 C A22 B11 ; P4 D A22 S4 D A22 B21 A22 B11 ; P5 D S5 S6 D A11 B11 C A11 B22 C A22 B11 C A22 B22 ; P6 D S7 S8 D A12 B21 C A12 B22 A22 B21 A22 B22 ; P7 D S9 S10 D A11 B11 C A11 B12 A21 B11 A21 B12 : Note that the only multiplications we need to perform are those in the middle column of the above equations. The right-hand column just shows what these products equal in terms of the original submatrices created in step 1. Step 4 adds and subtracts the Pi matrices created in step 3 to construct the four n=2 n=2 submatrices of the product C . We start with C11 D P5 C P4 P2 C P6 : 4.2 Strassen's algorithm for matrix multiplication 81 Expanding out the right-hand side, with the expansion of each Pi on its own line and vertically aligning terms that cancel out, we see that C11 equals A11 B11 C A11 B22 C A22 B11 C A22 B22 A22 B11 C A22 B21 A11 B22 A12 B22 A22 B22 A22 B21 C A12 B22 C A12 B21 A11 B11 which corresponds to equation (4.11). Similarly, we set C12 D P1 C P2 ; and so C12 equals A11 B12 A11 B22 C A11 B22 C A12 B22 C A12 B21 ; A11 B12 C A12 B22 ; corresponding to equation (4.12). Setting C21 D P3 C P4 makes C21 equal A21 B11 C A22 B11 A22 B11 C A22 B21 A21 B11 C A22 B21 ; corresponding to equation (4.13). Finally, we set C22 D P5 C P1 P3 P7 ; so that C22 equals A11 B11 C A11 B22 C A22 B11 C A22 B22 A11 B22 C A11 B12 A22 B11 A21 B11 A11 B11 A11 B12 C A21 B11 C A21 B12 A22 B22 C A21 B12 ; 82 Chapter 4 Divide-and-Conquer which corresponds to equation (4.14). Altogether, we add or subtract n=2 n=2 matrices eight times in step 4, and so this step indeed takes '.n2/ time. Thus, we see that Strassen's algorithm, comprising steps 1–4, produces the correct matrix product and that recurrence (4.18) characterizes its running time. Since we shall see in Section 4.5 that this recurrence has the solution T .n/ D '.nlg7/, Strassen's method is asymptotically faster than the straightforward SQUAREMATRIX-MULTIPLY procedure. The notes at the end of this chapter discuss some of the practical aspects of Strassen's algorithm. Exercises Note: Although Exercises 4.2-3, 4.2-4, and 4.2-5 are about variants on Strassen's algorithm, you should read Section 4.5 before trying to solve them. 4.2-1 Use Strassen's algorithm to compute the matrix product  Ã à 13 75 68 42 : Show your work. 4.2-2 Write pseudocode for Strassen's algorithm. 4.2-3 How would you modify Strassen's algorithm to multiply n n matrices in which n is not an exact power of 2? Show that the resulting algorithm runs in time '.nlg7/. 4.2-4 What is the largest k such that if you can multiply 3 3 matrices using k multiplications (not assuming commutativity of multiplication), then you can multiply n n matrices in time o.nlg 7/? What would the running time of this algorithm be? 4.2-5 V. Pan has discovered a way of multiplying 68 68 matrices using 132,464 multiplications, a way of multiplying 70 70 matrices using 143,640 multiplications, and a way of multiplying 72 72 matrices using 155,424 multiplications. Which method yields the best asymptotic running time when used in a divide-and-conquer matrix-multiplication algorithm? How does it compare to Strassen's algorithm? 4.3 The substitution method for solving recurrences 83 4.2-6 How quickly can you multiply a k n n matrix by an n k n matrix, using Strassen's algorithm as a subroutine? Answer the same question with the order of the input matrices reversed. 4.2-7 Show how to multiply the complex numbers a C bi and c C d i using only three multiplications of real numbers. The algorithm should take a, b, c, and d as input and produce the real component ac bd and the imaginary component ad C bc separately. 4.3 The substitution method for solving recurrences Now that we have seen how recurrences characterize the running times of divideand-conquer algorithms, we will learn how to solve recurrences. We start in this section with the "substitution" method. The substitution method for solving recurrences comprises two steps: 1. Guess the form of the solution. 2. Use mathematical induction to find the constants and show that the solution works. We substitute the guessed solution for the function when applying the inductive hypothesis to smaller values; hence the name "substitution method." This method is powerful, but we must be able to guess the form of the answer in order to apply it. We can use the substitution method to establish either upper or lower bounds on a recurrence. As an example, let us determine an upper bound on the recurrence T .n/ D 2T .bn=2c/ C n ; (4.19) which is similar to recurrences (4.3) and (4.4). We guess that the solution is T .n/ D O.n lg n/. The substitution method requires us to prove that T .n/ Ä cn lg n for an appropriate choice of the constant c > 0. We start by assuming that this bound holds for all positive m < n, in particular for m D bn=2c, yielding T .bn=2c/ Ä c bn=2c lg.bn=2c/. Substituting into the recurrence yields T .n/ Ä 2.c bn=2c lg.bn=2c// C n Ä cn lg.n=2/ C n D cn lg n cn lg 2 C n D cn lg n cn C n Ä cn lg n ; 84 Chapter 4 Divide-and-Conquer where the last step holds as long as c 1. Mathematical induction now requires us to show that our solution holds for the boundary conditions. Typically, we do so by showing that the boundary conditions are suitable as base cases for the inductive proof. For the recurrence (4.19), we must show that we can choose the constant c large enough so that the bound T .n/ Ä cn lg n works for the boundary conditions as well. This requirement can sometimes lead to problems. Let us assume, for the sake of argument, that T .1/ D 1 is the sole boundary condition of the recurrence. Then for n D 1, the bound T .n/ Ä cn lg n yields T .1/ Ä c1 lg 1 D 0, which is at odds with T .1/ D 1. Consequently, the base case of our inductive proof fails to hold. We can overcome this obstacle in proving an inductive hypothesis for a specific boundary condition with only a little more effort. In the recurrence (4.19), for example, we take advantage of asymptotic notation requiring us only to prove T .n/ Ä cn lg n for n n0, where n0 is a constant that we get to choose. We keep the troublesome boundary condition T .1/ D 1, but remove it from consideration in the inductive proof. We do so by first observing that for n > 3, the recurrence does not depend directly on T .1/. Thus, we can replace T .1/ by T .2/ and T .3/ as the base cases in the inductive proof, letting n0 D 2. Note that we make a distinction between the base case of the recurrence (n D 1) and the base cases of the inductive proof (n D 2 and n D 3). With T .1/ D 1, we derive from the recurrence that T .2/ D 4 and T .3/ D 5. Now we can complete the inductive proof that T .n/ Ä cn lg n for some constant c 1 by choosing c large enough so that T .2/ Ä c2 lg 2 and T .3/ Ä c3 lg 3. As it turns out, any choice of c 2 suffices for the base cases of n D 2 and n D 3 to hold. For most of the recurrences we shall examine, it is straightforward to extend boundary conditions to make the inductive assumption work for small n, and we shall not always explicitly work out the details. Making a good guess Unfortunately, there is no general way to guess the correct solutions to recurrences. Guessing a solution takes experience and, occasionally, creativity. Fortunately, though, you can use some heuristics to help you become a good guesser. You can also use recursion trees, which we shall see in Section 4.4, to generate good guesses. If a recurrence is similar to one you have seen before, then guessing a similar solution is reasonable. As an example, consider the recurrence T .n/ D 2T .bn=2c C 17/ C n ; which looks difficult because of the added "17" in the argument to T on the righthand side. Intuitively, however, this additional term cannot substantially affect the 4.3 The substitution method for solving recurrences 85 solution to the recurrence. When n is large, the difference between bn=2c and bn=2c C 17 is not that large: both cut n nearly evenly in half. Consequently, we make the guess that T .n/ D O.n lg n/, which you can verify as correct by using the substitution method (see Exercise 4.3-6). Another way to make a good guess is to prove loose upper and lower bounds on the recurrence and then reduce the range of uncertainty. For example, we might start with a lower bound of T .n/ D .n/ for the recurrence (4.19), since we have the term n in the recurrence, and we can prove an initial upper bound of T .n/ D O.n2/. Then, we can gradually lower the upper bound and raise the lower bound until we converge on the correct, asymptotically tight solution of T .n/ D '.n lg n/. Subtleties Sometimes you might correctly guess an asymptotic bound on the solution of a recurrence, but somehow the math fails to work out in the induction. The problem frequently turns out to be that the inductive assumption is not strong enough to prove the detailed bound. If you revise the guess by subtracting a lower-order term when you hit such a snag, the math often goes through. Consider the recurrence T .n/ D T .bn=2c/ C T .dn=2e/ C 1 : We guess that the solution is T .n/ D O.n/, and we try to show that T .n/ Ä cn for an appropriate choice of the constant c. Substituting our guess in the recurrence, we obtain T .n/ Ä c bn=2c C c dn=2e C 1 D cn C 1 ; which does not imply T .n/ Ä cn for any choice of c. We might be tempted to try a larger guess, say T .n/ D O.n2/. Although we can make this larger guess work, our original guess of T .n/ D O.n/ is correct. In order to show that it is correct, however, we must make a stronger inductive hypothesis. Intuitively, our guess is nearly right: we are off only by the constant 1, a lower-order term. Nevertheless, mathematical induction does not work unless we prove the exact form of the inductive hypothesis. We overcome our difficulty by subtracting a lower-order term from our previous guess. Our new guess is T .n/ Ä cn d , where d 0 is a constant. We now have T .n/ Ä .c bn=2c d / C .c dn=2e D cn 2d C 1 Ä cn d ; d/ C1 86 Chapter 4 Divide-and-Conquer as long as d 1. As before, we must choose the constant c large enough to handle the boundary conditions. You might find the idea of subtracting a lower-order term counterintuitive. After all, if the math does not work out, we should increase our guess, right? Not necessarily! When proving an upper bound by induction, it may actually be more difficult to prove that a weaker upper bound holds, because in order to prove the weaker bound, we must use the same weaker bound inductively in the proof. In our current example, when the recurrence has more than one recursive term, we get to subtract out the lower-order term of the proposed bound once per recursive term. In the above example, we subtracted out the constant d twice, once for the T .bn=2c/ term and once for the T .dn=2e/ term. We ended up with the inequality T .n/ Ä cn 2d C 1, and it was easy to find values of d to make cn 2d C 1 be less than or equal to cn d . Avoiding pitfalls It is easy to err in the use of asymptotic notation. For example, in the recurrence (4.19) we can falsely "prove" T .n/ D O.n/ by guessing T .n/ Ä cn and then arguing T .n/ Ä 2.c bn=2c/ C n Ä cn C n D O.n/ ; wrong!! since c is a constant. The error is that we have not proved the exact form of the inductive hypothesis, that is, that T .n/ Ä cn. We therefore will explicitly prove that T .n/ Ä cn when we want to show that T .n/ D O.n/. Changing variables Sometimes, a little algebraic manipulation can make an unknown recurrence similar to one you have seen before. As an example, consider the recurrence p˘ T .n/ D 2T n C lg n ; which looks difficult. We can simplify this recurrence, though, with a change of varpiables. For convenience, we shall not worry about rounding off values, such as n, to be integers. Renaming m D lg n yields T .2m/ D 2T .2m=2/ C m : We can now rename S.m/ D T .2m/ to produce the new recurrence S.m/ D 2S.m=2/ C m ; 4.3 The substitution method for solving recurrences 87 which is very much like recurrence (4.19). Indeed, this new recurrence has the same solution: S.m/ D O.m lg m/. Changing back from S.m/ to T .n/, we obtain T .n/ D T .2m/ D S.m/ D O.m lg m/ D O.lg n lg lg n/ : Exercises 4.3-1 Show that the solution of T .n/ D T .n 1/ C n is O.n2/. 4.3-2 Show that the solution of T .n/ D T .dn=2e/ C 1 is O.lg n/. 4.3-3 We saw that the solution of T .n/ D 2T .bn=2c/ C n is O.n lg n/. Show that the solution of this recurrence is also .n lg n/. Conclude that the solution is '.n lg n/. 4.3-4 Show that by making a different inductive hypothesis, we can overcome the difficulty with the boundary condition T .1/ D 1 for recurrence (4.19) without adjusting the boundary conditions for the inductive proof. 4.3-5 Show that '.n lg n/ is the solution to the "exact" recurrence (4.3) for merge sort. 4.3-6 Show that the solution to T .n/ D 2T .bn=2c C 17/ C n is O.n lg n/. 4.3-7 Using the master method in Section 4.5, you can show that the solution to the recurrence T .n/ D 4T .n=3/ C n is T .n/ D '.nlog3 4/. Show that a substitution proof with the assumption T .n/ Ä cnlog3 4 fails. Then show how to subtract off a lower-order term to make a substitution proof work. 4.3-8 Using the master method in Section 4.5, you can show that the solution to the recurrence T .n/ D 4T .n=2/ C n2 is T .n/ D '.n2/. Show that a substitution proof with the assumption T .n/ Ä cn2 fails. Then show how to subtract off a lower-order term to make a substitution proof work. 88 Chapter 4 Divide-and-Conquer 4.3-9 p Solve the recurrence T .n/ D 3T . n/ C log n by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral. 4.4 The recursion-tree method for solving recurrences Although you can use the substitution method to provide a succinct proof that a solution to a recurrence is correct, you might have trouble coming up with a good guess. Drawing out a recursion tree, as we did in our analysis of the merge sort recurrence in Section 2.3.2, serves as a straightforward way to devise a good guess. In a recursion tree, each node represents the cost of a single subproblem somewhere in the set of recursive function invocations. We sum the costs within each level of the tree to obtain a set of per-level costs, and then we sum all the per-level costs to determine the total cost of all levels of the recursion. A recursion tree is best used to generate a good guess, which you can then verify by the substitution method. When using a recursion tree to generate a good guess, you can often tolerate a small amount of "sloppiness," since you will be verifying your guess later on. If you are very careful when drawing out a recursion tree and summing the costs, however, you can use a recursion tree as a direct proof of a solution to a recurrence. In this section, we will use recursion trees to generate good guesses, and in Section 4.6, we will use recursion trees directly to prove the theorem that forms the basis of the master method. For example, let us see how a recursion tree would provide a good guess for the recurrence T .n/ D 3T .bn=4c/ C '.n2/. We start by focusing on finding an upper bound for the solution. Because we know that floors and ceilings usually do not matter when solving recurrences (here's an example of sloppiness that we can tolerate), we create a recursion tree for the recurrence T .n/ D 3T .n=4/ C cn2, having written out the implied constant coefficient c > 0. Figure 4.5 shows how we derive the recursion tree for T .n/ D 3T .n=4/ C cn2. For convenience, we assume that n is an exact power of 4 (another example of tolerable sloppiness) so that all subproblem sizes are integers. Part (a) of the figure shows T .n/, which we expand in part (b) into an equivalent tree representing the recurrence. The cn2 term at the root represents the cost at the top level of recursion, and the three subtrees of the root represent the costs incurred by the subproblems of size n=4. Part (c) shows this process carried one step further by expanding each node with cost T .n=4/ from part (b). The cost for each of the three children of the root is c.n=4/2. We continue expanding each node in the tree by breaking it into its constituent parts as determined by the recurrence. 4.4 The recursion-tree method for solving recurrences 89 T .n/ cn2 cn2 T n 4 T n 4 T n 4 c n2 4 c n2 4 c n2 4 T n 16 T n 16 T n 16 T n 16 T n 16 T n 16 T n 16 T n 16 T n 16 (a) (b) (c) cn2 c n2 4 c n2 4 c n2 4 log4 n c n2 16 c n2 16 c n2 16 c n2 16 c n2 16 c n2 16 c n2 16 c n2 16 c n2 16 cn2 3 16 cn2 3 16 2 cn2 … T .1/ T .1/ T .1/ T .1/ T .1/ T .1/ T .1/ T .1/ T .1/ T .1/ … T .1/ T .1/ T .1/ nlog4 3 (d) '.nlog4 3/ Total: O.n2/ Figure 4.5 Constructing a recursion tree for the recurrence T .n/ D 3T .n=4/ C cn2. Part (a) shows T .n/, which progressively expands in (b)–(d) to form the recursion tree. The fully expanded tree in part (d) has height log4 n (it has log4 n C 1 levels). 90 Chapter 4 Divide-and-Conquer Because subproblem sizes decrease by a factor of 4 each time we go down one level, we eventually must reach a boundary condition. How far from the root do we reach one? The subproblem size for a node at depth i is n=4i . Thus, the subproblem size hits n D 1 when n=4i D 1 or, equivalently, when i D log4 n. Thus, the tree has log4 n C 1 levels (at depths 0; 1; 2; : : : ; log4 n). Next we determine the cost at each level of the tree. Each level has three times more nodes than the level above, and so the number of nodes at depth i is 3i . Because subproblem sizes reduce by a factor of 4 for each level we go down from the root, each node at depth i, for i D 0; 1; 2; : : : ; log4 n 1, has a cost of c.n=4i /2. Multiplying, we see that the total cost over all nodes at depth i , for i D 0; 1; 2; : : : ; log4 n 1, is 3i c.n=4i /2 D .3=16/i cn2. The bottom level, at depth log4 n, has 3log4 n D nlog4 3 nodes, each contributing cost T .1/, for a total cost of nlog4 3T .1/, which is '.nlog4 3/, since we assume that T .1/ is a constant. Now we add up the costs over all levels to determine the cost for the entire tree: T .n/ D cn2 C 3 cn2 C  3 Ã2 cn2 C 16 16 D logX 4 n 1  3 Ãi cn2 C '.nlog4 3/ 16 i D0  3 C Ãlog4 n 1 cn2 C '.nlog4 3/ 16 .3=16/log4 n D 1 cn2 C '.nlog4 3/ .3=16/ 1 (by equation (A.5)) : This last formula looks somewhat messy until we realize that we can again take advantage of small amounts of sloppiness and use an infinite decreasing geometric series as an upper bound. Backing up one step and applying equation (A.6), we have T .n/ D logX 4 n 1  3 Ãi cn2 C '.nlog4 3/ 16 i D0 < X 1  3 Ãi cn2 C '.nlog4 3/ 16 i D0 D 1 cn2 C '.nlog4 3/ 1 .3=16/ D 16 cn2 C '.nlog4 3/ 13 D O.n2/ : Thus, we have derived a guess of T .n/ D O.n2/ for our original recurrence T .n/ D 3T .bn=4c/ C '.n2/. In this example, the coefficients of cn2 form a decreasing geometric series and, by equation (A.6), the sum of these coefficients 4.4 The recursion-tree method for solving recurrences 91 cn cn c n 3 c 2n 3 cn log3=2 n c n 9 c 2n 9 c 2n 9 c 4n 9 cn … … Total: O.n lg n/ Figure 4.6 A recursion tree for the recurrence T .n/ D T .n=3/ C T .2n=3/ C cn. is bounded from above by the constant 16=13. Since the root's contribution to the total cost is cn2, the root contributes a constant fraction of the total cost. In other words, the cost of the root dominates the total cost of the tree. In fact, if O.n2/ is indeed an upper bound for the recurrence (as we shall verify in a moment), then it must be a tight bound. Why? The first recursive call contributes a cost of '.n2/, and so .n2/ must be a lower bound for the recurrence. Now we can use the substitution method to verify that our guess was correct, that is, T .n/ D O.n2/ is an upper bound for the recurrence T .n/ D 3T .bn=4c/ C '.n2/. We want to show that T .n/ Ä d n2 for some constant d > 0. Using the same constant c > 0 as before, we have T .n/ Ä 3T .bn=4c/ C cn2 Ä 3d bn=4c2 C cn2 Ä 3d.n=4/2 C cn2 D 3 d n2 C cn2 16 Ä d n2 ; where the last step holds as long as d .16=13/c. In another, more intricate, example, Figure 4.6 shows the recursion tree for T .n/ D T .n=3/ C T .2n=3/ C O.n/ : (Again, we omit floor and ceiling functions for simplicity.) As before, we let c represent the constant factor in the O.n/ term. When we add the values across the levels of the recursion tree shown in the figure, we get a value of cn for every level. 92 Chapter 4 Divide-and-Conquer The longest simple path from the root to a leaf is n ! .2=3/n ! .2=3/2n ! ! 1. Since .2=3/kn D 1 when k D log3=2 n, the height of the tree is log3=2 n. Intuitively, we expect the solution to the recurrence to be at most the number of levels times the cost of each level, or O.cn log3=2 n/ D O.n lg n/. Figure 4.6 shows only the top levels of the recursion tree, however, and not every level in the tree contributes a cost of cn. Consider the cost of the leaves. If this recursion tree were a complete binary tree of height log3=2 n, there would be 2log3=2 n D nlog3=2 2 leaves. Since the cost of each leaf is a constant, the total cost of all leaves would then be '.nlog3=2 2/ which, since log3=2 2 is a constant strictly greater than 1, is !.n lg n/. This recursion tree is not a complete binary tree, however, and so it has fewer than nlog3=2 2 leaves. Moreover, as we go down from the root, more and more internal nodes are absent. Consequently, levels toward the bottom of the recursion tree contribute less than cn to the total cost. We could work out an accurate accounting of all costs, but remember that we are just trying to come up with a guess to use in the substitution method. Let us tolerate the sloppiness and attempt to show that a guess of O.n lg n/ for the upper bound is correct. Indeed, we can use the substitution method to verify that O.n lg n/ is an upper bound for the solution to the recurrence. We show that T .n/ Ä d n lg n, where d is a suitable positive constant. We have T .n/ Ä T .n=3/ C T .2n=3/ C cn Ä d.n=3/ lg.n=3/ C d.2n=3/ lg.2n=3/ C cn D .d.n=3/ lg n d.n=3/ lg 3/ C .d.2n=3/ lg n d.2n=3/ lg.3=2// C cn D d n lg n d..n=3/ lg 3 C .2n=3/ lg.3=2// C cn D d n lg n d..n=3/ lg 3 C .2n=3/ lg 3 .2n=3/ lg 2/ C cn D d n lg n d n.lg 3 2=3/ C cn Ä d n lg n ; as long as d c=.lg 3 .2=3//. Thus, we did not need to perform a more accurate accounting of costs in the recursion tree. Exercises 4.4-1 Use a recursion tree to determine a good asymptotic upper bound on the recurrence T .n/ D 3T .bn=2c/ C n. Use the substitution method to verify your answer. 4.4-2 Use a recursion tree to determine a good asymptotic upper bound on the recurrence T .n/ D T .n=2/ C n2. Use the substitution method to verify your answer. 4.5 The master method for solving recurrences 93 4.4-3 Use a recursion tree to determine a good asymptotic upper bound on the recurrence T .n/ D 4T .n=2 C 2/ C n. Use the substitution method to verify your answer. 4.4-4 Use a recursion tree to determine a good asymptotic upper bound on the recurrence T .n/ D 2T .n 1/ C 1. Use the substitution method to verify your answer. 4.4-5 Use a recursion tree to determine a good asymptotic upper bound on the recurrence T .n/ D T .n 1/CT .n=2/Cn. Use the substitution method to verify your answer. 4.4-6 Argue that the solution to the recurrence T .n/ D T .n=3/CT .2n=3/Ccn, where c is a constant, is .n lg n/ by appealing to a recursion tree. 4.4-7 Draw the recursion tree for T .n/ D 4T .bn=2c/ C cn, where c is a constant, and provide a tight asymptotic bound on its solution. Verify your bound by the substitution method. 4.4-8 Use a recursion tree to give an asymptotically tight solution to the recurrence T .n/ D T .n a/ C T .a/ C cn, where a 1 and c > 0 are constants. 4.4-9 Use a recursion tree to give an asymptotically tight solution to the recurrence T .n/ D T .˛ n/ C T ..1 ˛/n/ C cn, where ˛ is a constant in the range 0 < ˛ < 1 and c > 0 is also a constant. 4.5 The master method for solving recurrences The master method provides a "cookbook" method for solving recurrences of the form T .n/ D aT .n=b/ C f .n/ ; (4.20) where a 1 and b > 1 are constants and f .n/ is an asymptotically positive function. To use the master method, you will need to memorize three cases, but then you will be able to solve many recurrences quite easily, often without pencil and paper. 94 Chapter 4 Divide-and-Conquer The recurrence (4.20) describes the running time of an algorithm that divides a problem of size n into a subproblems, each of size n=b, where a and b are positive constants. The a subproblems are solved recursively, each in time T .n=b/. The function f .n/ encompasses the cost of dividing the problem and combining the results of the subproblems. For example, the recurrence arising from Strassen's algorithm has a D 7, b D 2, and f .n/ D '.n2/. As a matter of technical correctness, the recurrence is not actually well defined, because n=b might not be an integer. Replacing each of the a terms T .n=b/ with either T .bn=bc/ or T .dn=be/ will not affect the asymptotic behavior of the recurrence, however. (We will prove this assertion in the next section.) We normally find it convenient, therefore, to omit the floor and ceiling functions when writing divide-and-conquer recurrences of this form. The master theorem The master method depends on the following theorem. Theorem 4.1 (Master theorem) Let a 1 and b > 1 be constants, let f .n/ be a function, and let T .n/ be defined on the nonnegative integers by the recurrence T .n/ D aT .n=b/ C f .n/ ; where we interpret n=b to mean either bn=bc or dn=be. Then T .n/ has the following asymptotic bounds: 1. If f .n/ D O.nlogb a / for some constant > 0, then T .n/ D '.nlogb a/. 2. If f .n/ D '.nlogb a/, then T .n/ D '.nlogb a lg n/. 3. If f .n/ D .nlogb aC / for some constant > 0, and if af .n=b/ Ä cf .n/ for some constant c < 1 and all sufficiently large n, then T .n/ D '.f .n//. Before applying the master theorem to some examples, let's spend a moment trying to understand what it says. In each of the three cases, we compare the function f .n/ with the function nlogb a. Intuitively, the larger of the two functions determines the solution to the recurrence. If, as in case 1, the function nlogb a is the larger, then the solution is T .n/ D '.nlogb a/. If, as in case 3, the function f .n/ is the larger, then the solution is T .n/ D '.f .n//. If, as in case 2, the two func- tions are the same size, we multiply by a logarithmic factor, and the solution is T .n/ D '.nlogb a lg n/ D '.f .n/ lg n/. Beyond this intuition, you need to be aware of some technicalities. In the first case, not only must f .n/ be smaller than nlogb a, it must be polynomially smaller. 4.5 The master method for solving recurrences 95 That is, f .n/ must be asymptotically smaller than nlogb a by a factor of n for some constant > 0. In the third case, not only must f .n/ be larger than nlogb a, it also must be polynomially larger and in addition satisfy the "regularity" condition that af .n=b/ Ä cf .n/. This condition is satisfied by most of the polynomially bounded functions that we shall encounter. Note that the three cases do not cover all the possibilities for f .n/. There is a gap between cases 1 and 2 when f .n/ is smaller than nlogb a but not polynomially smaller. Similarly, there is a gap between cases 2 and 3 when f .n/ is larger than nlogb a but not polynomially larger. If the function f .n/ falls into one of these gaps, or if the regularity condition in case 3 fails to hold, you cannot use the master method to solve the recurrence. Using the master method To use the master method, we simply determine which case (if any) of the master theorem applies and write down the answer. As a first example, consider T .n/ D 9T .n=3/ C n : For this recurrence, we have a D 9, b D 3, f .n/ D n, and thus we have that nlogb a D nlog3 9 D '.n2). Since f .n/ D O.nlog3 9 /, where D 1, we can apply case 1 of the master theorem and conclude that the solution is T .n/ D '.n2/. Now consider T .n/ D T .2n=3/ C 1; in which a D 1, b D 3=2, f .n/ D 1, and nlogb a D nlog3=2 1 D n0 D 1. Case 2 applies, since f .n/ D '.nlogb a/ D '.1/, and thus the solution to the recurrence is T .n/ D '.lg n/. For the recurrence T .n/ D 3T .n=4/ C n lg n ; we have a D 3, b D 4, f .n/ D n lg n, and nlogb a D nlog4 3 D O.n0:793/. Since f .n/ D .nlog4 3C /, where 0:2, case 3 applies if we can show that the regularity condition holds for f .n/. For sufficiently large n, we have that af .n=b/ D 3.n=4/ lg.n=4/ Ä .3=4/n lg n D cf .n/ for c D 3=4. Consequently, by case 3, the solution to the recurrence is T .n/ D '.n lg n/. The master method does not apply to the recurrence T .n/ D 2T .n=2/ C n lg n ; even though it appears to have the proper form: a D 2, b D 2, f .n/ D n lg n, and nlogb a D n. You might mistakenly think that case 3 should apply, since 96 Chapter 4 Divide-and-Conquer f .n/ D n lg n is asymptotically larger than nlogb a D n. The problem is that it is not polynomially larger. The ratio f .n/=nlogb a D .n lg n/=n D lg n is asymptotically less than n for any positive constant . Consequently, the recurrence falls into the gap between case 2 and case 3. (See Exercise 4.6-2 for a solution.) Let's use the master method to solve the recurrences we saw in Sections 4.1 and 4.2. Recurrence (4.7), T .n/ D 2T .n=2/ C '.n/ ; characterizes the running times of the divide-and-conquer algorithm for both the maximum-subarray problem and merge sort. (As is our practice, we omit stating the base case in the recurrence.) Here, we have a D 2, b D 2, f .n/ D '.n/, and thus we have that nlogb a D nlog2 2 D n. Case 2 applies, since f .n/ D '.n/, and so we have the solution T .n/ D '.n lg n/. Recurrence (4.17), T .n/ D 8T .n=2/ C '.n2/ ; describes the running time of the first divide-and-conquer algorithm that we saw for matrix multiplication. Now we have a D 8, b D 2, and f .n/ D '.n2/, and so nlogb a D nlog2 8 D n3. Since n3 is polynomially larger than f .n/ (that is, f .n/ D O.n3 / for D 1), case 1 applies, and T .n/ D '.n3/. Finally, consider recurrence (4.18), T .n/ D 7T .n=2/ C '.n2/ ; which describes the running time of Strassen's algorithm. Here, we have a D 7, b D 2, f .n/ D '.n2/, and thus nlogb a D nlog2 7. Rewriting log2 7 as lg 7 and recalling that 2:80 < lg 7 < 2:81, we see that f .n/ D O.nlg 7 / for D 0:8. Again, case 1 applies, and we have the solution T .n/ D '.nlg 7/. Exercises 4.5-1 Use the master method to give tight asymptotic bounds for the following recurrences. a. T .n/ D 2T .n=4/ C 1. p b. T .n/ D 2T .n=4/ C n. c. T .n/ D 2T .n=4/ C n. d. T .n/ D 2T .n=4/ C n2. 4.6 Proof of the master theorem 97 4.5-2 Professor Caesar wishes to develop a matrix-multiplication algorithm that is asymptotically faster than Strassen's algorithm. His algorithm will use the divideand-conquer method, dividing each matrix into pieces of size n=4 n=4, and the divide and combine steps together will take '.n2/ time. He needs to determine how many subproblems his algorithm has to create in order to beat Strassen's algorithm. If his algorithm creates a subproblems, then the recurrence for the running time T .n/ becomes T .n/ D aT .n=4/ C '.n2/. What is the largest integer value of a for which Professor Caesar's algorithm would be asymptotically faster than Strassen's algorithm? 4.5-3 Use the master method to show that the solution to the binary-search recurrence T .n/ D T .n=2/ C '.1/ is T .n/ D '.lg n/. (See Exercise 2.3-5 for a description of binary search.) 4.5-4 Can the master method be applied to the recurrence T .n/ D 4T .n=2/ C n2 lg n? Why or why not? Give an asymptotic upper bound for this recurrence. 4.5-5 ? Consider the regularity condition af .n=b/ Ä cf .n/ for some constant c < 1, which is part of case 3 of the master theorem. Give an example of constants a 1 and b > 1 and a function f .n/ that satisfies all the conditions in case 3 of the master theorem except the regularity condition. ? 4.6 Proof of the master theorem This section contains a proof of the master theorem (Theorem 4.1). You do not need to understand the proof in order to apply the master theorem. The proof appears in two parts. The first part analyzes the master recurrence (4.20), under the simplifying assumption that T .n/ is defined only on exact powers of b > 1, that is, for n D 1; b; b2; : : :. This part gives all the intuition needed to understand why the master theorem is true. The second part shows how to extend the analysis to all positive integers n; it applies mathematical technique to the problem of handling floors and ceilings. In this section, we shall sometimes abuse our asymptotic notation slightly by using it to describe the behavior of functions that are defined only over exact powers of b. Recall that the definitions of asymptotic notations require that 98 Chapter 4 Divide-and-Conquer bounds be proved for all sufficiently large numbers, not just those that are powers of b. Since we could make new asymptotic notations that apply only to the set fbi W i D 0; 1; 2; : : :g, instead of to the nonnegative numbers, this abuse is minor. Nevertheless, we must always be on guard when we use asymptotic notation over a limited domain lest we draw improper conclusions. For example, proving that T .n/ D O.n/ when n is an exact power of 2 does not guarantee that T .n/ D O.n/. The function T .n/ could be defined as ( n if n D 1; 2; 4; 8; : : : ; T .n/ D n2 otherwise ; in which case the best upper bound that applies to all values of n is T .n/ D O.n2/. Because of this sort of drastic consequence, we shall never use asymptotic notation over a limited domain without making it absolutely clear from the context that we are doing so. 4.6.1 The proof for exact powers The first part of the proof of the master theorem analyzes the recurrence (4.20) T .n/ D aT .n=b/ C f .n/ ; for the master method, under the assumption that n is an exact power of b > 1, where b need not be an integer. We break the analysis into three lemmas. The first reduces the problem of solving the master recurrence to the problem of evaluating an expression that contains a summation. The second determines bounds on this summation. The third lemma puts the first two together to prove a version of the master theorem for the case in which n is an exact power of b. Lemma 4.2 Let a 1 and b > 1 be constants, and let f .n/ be a nonnegative function defined on exact powers of b. Define T .n/ on exact powers of b by the recurrence ( '.1/ if n D 1 ; T .n/ D aT .n=b/ C f .n/ if n D bi ; where i is a positive integer. Then logX b n 1 T .n/ D '.nlogb a/ C aj f .n=bj / : j D0 (4.21) Proof We use the recursion tree in Figure 4.7. The root of the tree has cost f .n/, and it has a children, each with cost f .n=b/. (It is convenient to think of a as being 4.6 Proof of the master theorem f .n/ a f .n=b/ f .n=b/ … f .n=b/ a a logb n f .n=b2/f .n=b2/…f .n=b2/ f .n=b2/f .n=b2/…f .n=b2/ a f .n=b2/f .n=b2/…f .n=b2/ a a a …… … a a a …… … a a a …… … 99 f .n/ af .n=b/ a2f .n=b2/ … '.1/ '.1/ '.1/ '.1/ '.1/ '.1/ '.1/ '.1/ '.1/ '.1/ … '.1/ '.1/ '.1/ '.nlogb a/ nlogb a logX b n 1 Total: '.nlogb a/ C aj f .n=bj / j D0 Figure 4.7 The recursion tree generated by T .n/ D aT .n=b/ C f .n/. The tree is a complete a-ary tree with nlogb a leaves and height logb n. The cost of the nodes at each depth is shown at the right, and their sum is given in equation (4.21). an integer, especially when visualizing the recursion tree, but the mathematics does not require it.) Each of these children has a children, making a2 nodes at depth 2, and each of the a children has cost f .n=b2/. In general, there are aj nodes at depth j , and each has cost f .n=bj /. The cost of each leaf is T .1/ D '.1/, and each leaf is at depth logb n, since n=blogb n D 1. There are alogb n D nlogb a leaves in the tree. We can obtain equation (4.21) by summing the costs of the nodes at each depth in the tree, as shown in the figure. The cost for all internal nodes at depth j is aj f .n=bj /, and so the total cost of all internal nodes is logX b n 1 aj f .n=bj / : j D0 In the underlying divide-and-conquer algorithm, this sum represents the costs of dividing problems into subproblems and then recombining the subproblems. The 100 Chapter 4 Divide-and-Conquer cost of all the leaves, which is the cost of doing all nlogb a subproblems of size 1, is '.nlogb a/. In terms of the recursion tree, the three cases of the master theorem correspond to cases in which the total cost of the tree is (1) dominated by the costs in the leaves, (2) evenly distributed among the levels of the tree, or (3) dominated by the cost of the root. The summation in equation (4.21) describes the cost of the dividing and combining steps in the underlying divide-and-conquer algorithm. The next lemma provides asymptotic bounds on the summation's growth. Lemma 4.3 Let a 1 and b > 1 be constants, and let f .n/ be a nonnegative function defined on exact powers of b. A function g.n/ defined over exact powers of b by logX b n 1 g.n/ D aj f .n=bj / j D0 (4.22) has the following asymptotic bounds for exact powers of b: 1. If f .n/ D O.nlogb a / for some constant > 0, then g.n/ D O.nlogb a/. 2. If f .n/ D '.nlogb a/, then g.n/ D '.nlogb a lg n/. 3. If af .n=b/ Ä cf .n/ for some constant c < 1 and for all sufficiently large n, then g.n/ D '.f .n//. Proof For case 1, we have f .n/ D O.nlogb a /, which implies that f .n=bj / D O..n=bj /logb a /. Substituting into equation (4.22) yields logX b n 1 g.n/ D O aj n Álogb a ! : bj j D0 (4.23) We bound the summation within the O-notation by factoring out terms and simpli- fying, which leaves an increasing geometric series: logX b n 1 aj j D0 n Álogb a bj D nlogb a logX b n 1  ab Ãj j D0 blogb a logX b n 1 D nlogb a .b /j D nlogb a ÂjbD0logb n à 1 b1 4.6 Proof of the master theorem 101  D nlogb a n b à 1 : 1 Since b and are constants, we can rewrite the last expression as nlogb a O.n / D O.nlogb a/. Substituting this expression for the summation in equation (4.23) yields g.n/ D O.nlogb a/ ; thereby proving case 1. Because case 2 assumes that f .n/ D '.nlogb a/, we have that f .n=bj / D '..n=bj /logb a/. Substituting into equation (4.22) yields g.n/ D ' logX b n 1 aj j D0 n Álogb ! a : bj (4.24) We bound the summation within the '-notation as in case 1, but this time we do not obtain a geometric series. Instead, we discover that every term of the summation is the same: logX b n 1 aj n Álogb a D logX b n 1 nlogb a a Áj bj blogb a j D0 j D0 logX b n 1 D nlogb a 1 j D0 D nlogb a logb n : Substituting this expression for the summation in equation (4.24) yields g.n/ D '.nlogb a logb n/ D '.nlogb a lg n/ ; proving case 2. We prove case 3 similarly. Since f .n/ appears in the definition (4.22) of g.n/ and all terms of g.n/ are nonnegative, we can conclude that g.n/ D .f .n// for exact powers of b. We assume in the statement of the lemma that af .n=b/ Ä cf .n/ for some constant c < 1 and all sufficiently large n. We rewrite this assumption as f .n=b/ Ä .c=a/f .n/ and iterate j times, yielding f .n=bj / Ä .c=a/j f .n/ or, equivalently, aj f .n=bj / Ä cj f .n/, where we assume that the values we iterate on are sufficiently large. Since the last, and smallest, such value is n=bj 1, it is enough to assume that n=bj 1 is sufficiently large. Substituting into equation (4.22) and simplifying yields a geometric series, but unlike the series in case 1, this one has decreasing terms. We use an O.1/ term to 102 Chapter 4 Divide-and-Conquer capture the terms that are not covered by our assumption that n is sufficiently large: logX b n 1 g.n/ D aj f .n=bj / j D0 logX b n 1 Ä cj f .n/ C O.1/ j D0 X 1 Ä f .n/ cj C O.1/ jÂD0 à 1 D f .n/ C O.1/ 1c D O.f .n// ; since c is a constant. Thus, we can conclude that g.n/ D '.f .n// for exact powers of b. With case 3 proved, the proof of the lemma is complete. We can now prove a version of the master theorem for the case in which n is an exact power of b. Lemma 4.4 Let a 1 and b > 1 be constants, and let f .n/ be a nonnegative function defined on exact powers of b. Define T .n/ on exact powers of b by the recurrence ( T .n/ D '.1/ if n D 1 ; aT .n=b/ C f .n/ if n D bi ; where i is a positive integer. Then T .n/ has the following asymptotic bounds for exact powers of b: 1. If f .n/ D O.nlogb a / for some constant > 0, then T .n/ D '.nlogb a/. 2. If f .n/ D '.nlogb a/, then T .n/ D '.nlogb a lg n/. 3. If f .n/ D .nlogb aC / for some constant > 0, and if af .n=b/ Ä cf .n/ for some constant c < 1 and all sufficiently large n, then T .n/ D '.f .n//. Proof We use the bounds in Lemma 4.3 to evaluate the summation (4.21) from Lemma 4.2. For case 1, we have T .n/ D '.nlogb a/ C O.nlogb a/ D '.nlogb a/ ; 4.6 Proof of the master theorem 103 and for case 2, T .n/ D '.nlogb a/ C '.nlogb a lg n/ D '.nlogb a lg n/ : For case 3, T .n/ D '.nlogb a/ C '.f .n// D '.f .n// ; because f .n/ D .nlogb aC /. 4.6.2 Floors and ceilings To complete the proof of the master theorem, we must now extend our analysis to the situation in which floors and ceilings appear in the master recurrence, so that the recurrence is defined for all integers, not for just exact powers of b. Obtaining a lower bound on T .n/ D aT .dn=be/ C f .n/ (4.25) and an upper bound on T .n/ D aT .bn=bc/ C f .n/ (4.26) is routine, since we can push through the bound dn=be n=b in the first case to yield the desired result, and we can push through the bound bn=bc Ä n=b in the second case. We use much the same technique to lower-bound the recurrence (4.26) as to upper-bound the recurrence (4.25), and so we shall present only this latter bound. We modify the recursion tree of Figure 4.7 to produce the recursion tree in Figure 4.8. As we go down in the recursion tree, we obtain a sequence of recursive invocations on the arguments n; dn=be ; ddn=be =be ; dddn=be =be =be ; ::: Let us denote the j th element in the sequence by nj , where ( nj D n if j D 0 ; dnj 1=be if j > 0 : (4.27) 104 Chapter 4 Divide-and-Conquer f .n/ a f .n1/ a blogb nc f .n2/ f .n2/ … f .n2/ a a a …… … f .n1/ … f .n1/ a a f .n2/ f .n2/ … f .n2/ a a a …… … f .n2/ f .n2/ … f .n2/ a a a …… … f .n/ af .n1/ a2f .n2/ … '.1/ '.1/ '.1/ '.1/ '.1/ '.1/ '.1/ '.1/ '.1/ '.1/ … '.1/ '.1/ '.1/ '.nlogb a/ '.nlogb a/ X blogb nc 1 Total: '.nlogb a/ C aj f .nj / j D0 Figure 4.8 The recursion tree generated by T .n/ D aT .dn=be/Cf .n/. The recursive argument nj is given by equation (4.27). Our first goal is to determine the depth k such that nk is a constant. Using the inequality dxe Ä x C 1, we obtain n0 Ä n ; n n1 Ä C1; b n1 n2 Ä C C1; b2 b n 11 n3 Ä C C C1; b3 b2 b ::: In general, we have 4.6 Proof of the master theorem 105 n X j 1 1 nj Ä C bj bi i D0 n X 1 1


text:
Deep House Progressive House
Hernan Cattaneo Resident 306 (March 2017)58:3397 221 Reshare SocialAddDownloadto Set to Group to Playlist58:33
Ryan Davis & Microtrauma - Traces (Gabriel Ananda Remix)53:200
● Welcome Page: facebook.com/progressivehouseo...useofficialpage
This track was tagged with the following keywords: Deep House.
1 liked it. 8 played it. 5 downloaded it.
Listen to all music and sounds of Progressive House and follow this user by signing in for free.
Deep House

subset: commoncrawl


text:
If you are looking for new investment opportunities or options, checkout our below our most updated 2018 list of brokerages bonuses, deals, and promotions such as TD Ameritrade, E*Trade, Schwab, Merrill Edge, Fidelity, Capital One Investing, Motif, and many more.
Johnson Makes Rare Speech as Fidelity Deals With
4/16/2018 · News & Events: GE. GENERAL ELECTRIC is exploring a public offering for one of its divisions and discussing hybrid deals with public Fidelity is not
Fidelity Ends Card Partnership With AmEx, BofA in Visa
Fidelity Investments is firing Most popular on BostonGlobe Tyrrell believes new ways of matching companies with investors are going to change the way deals
M&A Activity Heats up for Independent Broker-Dealers
Fidelity also provides comprehensive tools and educational resources on making mutual fund investments. Fees: Fidelity Fidelity Investments deals , tips and
Fidelity Investments Review: Best Broker for Long-Term
Fidelity's fixed income research tools can help you find the right bonds, CDs, bond funds, Both deals are rated AA-plus by Fitch.
FACTS What do Fidelity Investments and the Fidelity Funds
Fidelity International, formerly Fidelity Fidelity International handles investments for to allow shareholders to veto bonus deals for
Amazon.com: Customer reviews: Fidelity Investments
Fidelity International - Wikipedia
Store Deals Log in. 7 Best Fidelity Index Funds for the Money. Fidelity also offers a full roster of funds that merely try to match a benchmark.
Investment ISA | Save with a Stocks and Shares ISA | Fidelity
Fidelity Investments has hired an outside consultant to review inappropriate employee behavior in its equity unit, according to individuals familiar with the company.
About Fidelity International | Investment & Retirement
Jim Lowell is Editor-in-Chief of the award-winning independent newsletters Fidelity Investor and Fidelity Sector performance from their Fidelity investments.
Fidelity taking aim at Wall Street's IPO 'monopoly' - The
Fidelity's fixed income research tools can help you find the The total is comprised of $4.70 billion of competitive sales and $4.94 billion of negotiated deals.
7 Best Fidelity Mutual Funds for Retirement | InvestorPlace
Today's top Fidelity Investments coupon: see Our Featured Trading Offer. Get 5 coupons for 2018.
How the owners of Fidelity get richer at everyday
Looking for cheap index funds? What about smart active management? Fidelity Investments offers plenty from both columns via their vast array of mutual funds.
Fidelity vs. Schwab: Excellent Options for Beginner and
Forms, tools, resources, and other information you need for tax planning and filing.
UPDATE 1-Fidelity chairman deals with fallout from sexual
How Fidelity's rumored new partnerships would significantly hurt American Express
Welcome to 401k.com - Fidelity Investments
What are the benefits of investing your money with Fidelity? Read here to learn about the benefits of investing with the financial advisors you trust at Fidelity Investments
Huge Bonus Offers From Brokers: TD Ameritrade, ETrade
Fidelity Investments is now using virtual reality as part of its training. The company says it's helpful with millennials.
Fidelity deals with fallout after sex harassment
The financial world may have its own problems with sexual harassment. The manager of Fidelity Investments' stock-picking unit held an emergency meeting last week to reiterate the firm's policies against sexual harassment and inappropriate behavior, a …
Fidelity Investments Starts National Pilot of Its Robo
Less than a year into her tenure as chairman of Fidelity Investments, Abigail Johnson faces a crisis amid allegations that the mutual fund giant has a men's club mentality.
Log In to Fidelity Investments
Fidelity International has been helping customers make the right choices for investment funds, ISAs and personal pensions for over 45 years. Find out more.


text:
Wednesday, May 25, 2011
Israeli song becomes Syrian opposition's soundtrack
Three songs on Israeli singer Amir Benayoun's new Arabic-language album written at Syrian dissidents' request.
Bashar Assad has blamed his country's turmoil on Israel, but it's doubtful the Syrian autocrat had this in mind.
At the request of Syrian opposition leaders, Israeli singer Amir Benayoun has recorded three songs in Arabic and dedicated them to activists in the Syrian uprising.
One of the songs, "Zini," has already become a YouTube hit and serves as the soundtrack on a number of Syrian opposition leaders' Facebook pages.
The three tracks are part of an album – also called Zini – released earlier this month on Benayoun's label, Nevel Asor. The album's songs, all in Arabic, are adaptations of the Book of Ecclesiastes translated with the help of Benayoun's Algerian-born father, Maxim.
In February, "Zenga Zenga," a pop mash-up by Israeli DJ Noy Alooshe, became an Internet sensation and the unofficial anthem of the revolt against Libyan dictator Muammar Gaddafi. That success inspired Syrian opposition leaders to ask Ayoub Kara, deputy minister for development of the Negev and Galilee, whether he could convince Benayoun to record a similar track for their own protest movement.
Click To View Video
Kara said Benayoun is wellknown in Syria, and that he had previously received requests from Syrian opposition figures to translate the singer's songs into Arabic.
Benayoun added the three tracks to his album, and Kara distributed the CD to the leaders of 15 Syrian opposition groups at a meeting earlier this month in Turkey.
Since then the song "Zini" has become something of an anti-government rallying cry. One YouTube clip of the song uploaded by "akhbaralarab," a user in the United Arab Emirates, has logged over 1,500 views. Other clips use the track as background music to overlay scenes of Assad's violent crackdown on protesters.
Benayoun said the album is aimed at young Arabs in Israel and across the region.
"What would most move me is that you see someone who is not from your religion or people coming and asking for help, and them beginning to see that their leaders don't really love them but are oppressing them," he told The Jerusalem Post on Wednesday.
"B'ezrat Hashem [with God's help], they'll understand what Israel is and what we're about."
The singer, 35, first hit the Israeli charts in 1999 with the album Only You, a selection of Mizrahi, or Middle Easternstyle, ballads. In subsequent years he became more religiously observant and closely affiliated with the Chabad movement.
Today he's identified with the right wing of the religious Zionist camp, and last year released the song "I'm Your Brother," a musical assault on left-wing Israelis whom he accused of compromising national security.
Last month he recorded the single "I Shook" with members of the children's choir of Itamar. The song is in remembrance of the five members of the Fogel family murdered by terrorists in their home in the West Bank settlement in March.
Benayoun will make his live-performance debut of "Zini" on Tuesday night in Caesarea.
Posted by The Shining Star at 6:39 PM


text:
Our Company About Us Contact Us Community Treehouse Stories Student Perks Treehouse Blog Affiliate Program Careers Topics HTML CSS Design JavaScript Ruby PHP WordPress iOS Android Development Tools Business Tracks Web Thank you so much! –Eric Cochran Jun 29 '14 at 0:34 2 @Helix See above Ans.. Error:(2) Error retrieving parent for item: No resource found that matches the given name '@android:style/Theme.Material.Light'. 1 Answer Gian Lazzarini 1,493 Points Gian Lazzarini Gian Lazzarini 1,493 Points 8 months ago Wow... April 27, 2016 at 12:45 PM Post a Comment Newer Post Older Post Home Subscribe to: Post Comments (Atom) My Free Tools Create Marker Shadow GDM2000-BRSO(GRS80) Coordinates Converter GDM2000-MRSO(GRS80) Coordinates Converter this content
Sorry, I have no idea where is it in other OS. permalinkembedsavegive gold[–][deleted] 0 points1 point2 points 2 years ago(0 children)protip: please use something like https://gist.github.com/ to paste text-based samples in the future, it makes it easier for other people to try or example. Please sign in or sign up to post. I presumed command line –mindeh Nov 5 '13 at 23:19 ANDROID_HOME is set. http://stackoverflow.com/questions/19781054/android-studio-build-gradle-cannot-resolve-symbol-android
My project compiles and runs fine but I really need the autocomplete working!! editing, debugging) will not work properly" 4 Android project compiles, but maven dependencies not recognized in Android Studio see more linked questions… Related 824R cannot be resolved - Android error688Android Studio: Browse other questions tagged java android android-studio intellij-idea android-gradle or ask your own question.
How to create and use an Android Archive (*.aar) using Android Studio Besides a plain old Java archive file (*.jar), Android Studio can be used to create an Android archive file Clean Project again and done! In the Build Tools Version field, choose the latest version, e.g. 21.1.1. Android Studio Cannot Resolve Symbol Menu Can clients learn their time zone on a network configured using RA?
Para poder utilizar los foros de debate de Grupos de Google, debes habilitar JavaScript en la configuración del navegador y, a continuación, actualizar la página. . Android Studio Cannot Resolve Symbol String Thanks! I was having an issue with the support library at one point, I assumed it had something to do with my build.gradle. If you find any red circles with exclamation mark, than you must remove those errors in your code.Mostly these errors are related to @string/ or @array/.
Screenshot: java android android-studio intellij-idea android-gradle share|improve this question edited Sep 9 '15 at 10:42 asked Sep 9 '15 at 10:26 Jim C 1,2361310 try to use gradle clean Cannot Resolve Symbol Java Is this Business or Tourism? Start indexing of the project. Submit feedback to IBM Support 1-800-IBM-7378 (USA) Directory of worldwide contacts Contact Privacy Terms of use Accessibility About Geospatial Applications, Intergraph GeoMedia, FME, Visual Studio, gvSIG, Global Mapper, Programming, LiDAR, GIS,
asked 3 years ago viewed 55824 times active 2 days ago Upcoming Events 2016 Community Moderator Election ends Nov 22 Get the weekly newsletter! https://www.reddit.com/r/androiddev/comments/1ywjmh/buildgradle_cant_resolve_symbols/ I don't really know what happened in the background but when Android Studio started up again the status bar said Indexing... Cannot Resolve Symbol 'android' In Android Studio Draw a hollow square of # with given width Need to change cash to cashier's check without bank account (Just arrived to the US) How do fonts work in LaTeX? Android Studio Cannot Resolve Symbol Class Btw, do you run this from command line or IDE?
are up to date (tried with both v22.+ and v23.+ of the libraries). news The solution is to change the project settings to build using the latest Android SDK, as described below. I didn't have much luck with Android Studio 0.3.1. share|improve this answer edited Jan 24 '14 at 20:10 answered Jan 13 '14 at 20:39 Scott Barta 52.6k14131128 Wow that answer was beautiful thanks so damn much it seems Android Studio Cannot Resolve Symbol Activity
This will be fixed at some point, I'm sure. This will need to be amended if anything doesn't follow that pattern. –doydoy Jan 15 '15 at 22:08 add a comment| up vote 2 down vote When i lived to this There may be some lingering problems; if you see them in 0.4.3, let us know, and try to give us a reliable set of steps to reproduce so we can ensure http://peakgroup.net/cannot-resolve/cannot-resolve-symbol-c.php It is possible to define metric spaces from pure topological concepts without the need to define a distance function?
Our mission is to bring affordable, technology education to people everywhere, in order to help them achieve their dreams and change the world. Android Studio Cannot Resolve Symbol 'button What movie is this? I have also tried reinstalling android studio and reimporting the project.
Now I really want to us this code in Android Studio.
buildscript { repositories { mavenCentral() } dependencies { classpath 'com.android.tools.build:gradle:0.6.+' } } apply plugin: 'android' repositories { mavenCentral() } android { compileSdkVersion 19 buildToolsVersion "17.0.0" defaultConfig { minSdkVersion 7 targetSdkVersion 18 I have the "cannot resolve symbol" syntax highlighting problem with the classes from Android libraries such as android.support.v7.app, android.support.v4.app, and Google Play Services, which I have included as dependencies. Try our newsletter Sign up for our newsletter and get our top new questions delivered to your inbox (see an example). check my blog Top Post of the Month How to create and use an Android Archive (*.aar) using Android Studio Besides a plain old Java archive file (*.jar), Android Studio can be used to
share|improve this answer edited Jul 5 at 17:44 Alastair 3,94122123 answered May 19 '15 at 22:29 Georgi Dimitrov 412 it's brilliant work. I will bookmark your site thanks... Thanks to this guy: http://stackoverflow.com/a/33978721/425238 share|improve this answer answered Oct 8 at 15:34 whitebrow 618613 add a comment| protected by Community♦ Mar 16 '15 at 15:52 Thank you for your interest The directory structure MUST be : [project]\[module]\src\main\java\[yourpackage]\[yourclass.java] share|improve this answer answered Oct 7 '14 at 12:29 Rémy DAVID 2,08841220 add a comment| up vote 0 down vote I have finally figured
Not the answer you're looking for? To critique or request clarification from an author, leave a comment below their post - you can always comment on your own posts, and once you have sufficient reputation you will doing a 'gradlew clean' from the terminal would fail and throw a RunTimeException.). I think Android Studio is not able to import the dependent libraries for syntax highlighting, although the compiler is able to include them and build successfully.
Once I pointed the project back to the SDK location in Android Studio's install location the problem went away. share|improve this answer edited Sep 3 '14 at 8:41 Manu 1,58042761 answered Sep 3 '14 at 8:23 opened_eyes_media 111 add a comment| up vote 0 down vote I faced similar problem share|improve this answer edited May 9 '14 at 10:15 answered Oct 22 '13 at 12:11 doydoy 1,71821019 3 That did it! share|improve this answer answered Nov 14 '15 at 7:28 user3341089 1537 add a comment| up vote 1 down vote I had the very same problem recently with Android Studio 1.3.
Couple of wild guesses - try upgrading Gradle to 0.8 if its older (config requires merely 0.6); also check if environment variable for Android home is set: e.g.


text:
On Monday, we had the privilege of being asked to evangelise at the Redlands Easter Family Festival. With about 20,000 people expected to be there, we knew it would be a great day to get gospel tracts out and speak to many people.
This is a 2 minute report from the festival:
To our faithful King!
View previous Special Outreaches report (4 August 2012)


text: ThatsRacin He loved his country so much he died for it. Here's how NASCAR is honoring him. What's behind the name on Brad Keselowski's car? NASCAR drivers in the Coca-Cola 600 will honor fallen military members with their names on the windshields. Hickory's Chris Eckard, a Marine killed in Afghanistan, is among those honored.


text:
Manchester United parted company with David Moyes this morning and now begin the hunt for a permanent successor.
Plenty of names have been banded about already, with Netherlands coach Louis van Gaal the early frontrunner and Borussia Dortmund boss Jurgen Klopp ruling himself out of contention for the biggest job in English football.
Meanwhile, the bookmakers' odds for about a hundred different managers are shortening one minute and drifting the next.
Taken the odds from SkyBet and Paddy Power, we've assembled a list of some of the more unlikely candidates to replace Moyes this summer.
Who do you think will replace Moyes? Have your say in the comments section below!
Do YOU want to write for GiveMeSport? Get started today by signing-up and submitting an article HERE: https://www.givemesport.com/writeforgms


text:
From Prison Planet and Raw Story.
Afghan President Hamid Karzai on Sunday defended his decision to ban private security contractors from operating in public in Afghanistan, saying many of the organizations tasked with providing security are engaging in terrorist activities, working with "Mafia-like" organizations and "looting and stealing from the Afghan people."
Karzai also speculated that some groups may be acting as security contractors during the day and as terrorist groups "at nighttime."...
Monday, August 23, 2010
Karzai: Private contractors 'looting and stealing,' working "as terrorist groups at night time."
Posted by George at 5:12 PM
Labels: afghanistan, hamid karzai, mafia, private contractors, terrorist groups
Subscribe to: Post Comments (Atom)