15-451 Algorithms: Lecture 1/20/00 Announcements: Homework Assignment #1 is on the web page. Due Tues Feb 1. - Written HW: 4 Practice Problems plus 5 Hand-in Problems. - Give url with photo of yourself, or attach photo, when turn in HW #1. First recitation tonight 6:30 pm Wean 8427 Added second recitation session, on Monday. Covers same material as Thurs. ********** Topics: I. Asymptotic analysis: O, Omega, Theta, o, little-omega II. Recurrences: - Examples where they arise - Direct Methods for solving: unrolling, guess and induction proof, build recursion tree - A Helpful Formula for solving ********** I. Asymptotic Analysis Running time of algorithms. Analyze in terms of size of input, n. Focus will primarily be: how does the running time *scale* with the input size? - called "asymptotic analysis" - ignore low-order terms and constant factors (including issues like the relative cost of a comparison versus an array dereference); look at running time as a function of n in the limit as n gets large. Notation: O, Theta, Omega, little-o, little-omega T(n) is O(f(n)) if there exist constants c, n_0 > 0 such that T(n) <= c*f(n) for all n >= n_0 E.g. 3n^2 + 5n is O(n^2). For what values of c? Take any c > 3. Taking c=4, what is the smallest such n_0? 3n^2 + 5n <= 4n^2 iff 5n <= n^2 iff 5 <= n. Thus take n_0 = 5. E.g., 5n is O(n^2) and is also O(n). Formally, "T(n) is an element of O(f(n))". E.g., O(n^2) is a set of functions, and the definition above is telling us which functions are in the set. But, convention is to write T(n) = O(f(n)), which is a little confusing. Why? Because not symmetric: 5n = O(n) but O(n) ^= 5n. If its gets confusing to you, use set notation. T(n) is Omega(f(n)) if there exist constants c, n_0 > 0 such that T(n) >= c*f(n) for all n >= n_0 E.g., 3n^2 - 2n is Omega(n^2). E.g., we'll prove: Any comparison-based sorting algorithm must take Omega(n log n) time in worst case. T(n) is Theta( f(n) ) if it is both O(f(n)) AND Omega(f(n)). E.g., running time of mergesort is Theta(n log n). T(n) is o(f(n)) if for all constants c > 0, there exists a constant n_0 > 0 s.t. T(n) < c*f(n) for all n >= n_0. E.g., As we saw last time, Multiplying two n-bit numbers is o(n^2) time. Here's a sometimes easier way to think of it. Imagine plotting the ratio of T(n)/f(n) and looking in the limit as n->infinity. infinity --> CASE A lim T(n) / f(n) == number > 0 (e.g., 17) --> CASE B n->inf 0 --> CASE C CASE B or C: T(n) is O(f(n)) CASE A or B: T(n) is Omega(f(n)) CASE B: T(n) is Theta(f(n)). CASE C: T(n) is o(f(n)). CASE A: T(n) is little-omega(f(n)). (We won't be using this much.) Informally, "O" is like <=, "Omega" is like >=, "Theta" is like =, "o" is like <, and "little-omega" is like >. An example: - T(n) = 2n^3 + 100n^2 log(n) + 17n, f(n) = n^3. limit of [2n^3 + 100 n log(n) + 17 n]/n^3 = 2 + lim[(100log(n)/n^2 + 17/n^2] = 2. Thus T(n) = Theta(n^3). Technical point: What if limit does not exist? E.g., T(n) = n(2+sin(n))? By formal defn, T(n) = Theta(n). Why? Because n <= T(n) <= 3n for all n >= 1. Thus its Theta(n), even though there's no true limit. A typical use might be for a problem P, "we prove that *any* algorithm for P must take Omega(n log n) time in the worst case. My algorithm A for P takes O(n log n) time in the worst case. Thus, A is asymptotically optimal." ********** II. Recurrences We often are interested in algorithms expressed in a recursive way. When we analyze them, gives a recurrence: running time on input of size n, T(n), as a function of n *and* running time on inputs of smaller sizes. T(n) = f(n,T(n)), for n < n. Examples: 1. Mergesort: To sort an array of size n, we sort left half, sort right half, then merge the two results. We can do the merge in linear time. So, if T(n) is running time on input of size n, what recurrence do we get? T(n) = 2T(n/2) + cn What about the base case of the recurrence? Here, if the array has 0 or 1 elements, we just return: T(1) is constant. In general, base cases almost always of the form "If n < constant n_0, then do brute force, which takes a constant amount of time". Usually T(1) = c suffices. What about "integrality" issue? Some discussion in book. We'll basically ignore it, knowing (having thought it through) that it doesn't matter. 2. Selection sort: run through array A finding smallest. Put in leftmost position. Recursively sort A[2..n]. What's the recurrence? T(n) = cn + T(n-1). 3. Multiplication: Split into left and right halves. Straightforward way to solve the subproblems gave us: T(n) = 4T(n/2) + cn. But, rearranging terms in a clever way improved this to: T(n) = 3T(n/2) + cn. ************** How do we solve these? Give 4 methods. - solving by unrolling - solving by guess and inductive proof - solving by building recursion tree - helpful "master" formula 1. solving by unrolling Many times, the easiest way to solve is to unroll the recurrence, to get a summation. E.g., the one for selection sort gives us: T(n) = cn + c(n-1) + c(n-2) + ... + c = Theta(what?) What about T(n) = n^5 + T(n-1)? Solves to Theta(n^6). What's the proof? Can see "O()" since we have n terms, each of which is at most n^5. Can see "Omega()" since if we look at the top n/2 terms, each of them is at least (n/2)^5 Or, think of this like a discrete integral. 2. solving by guess and inductive proof. Say we have a recurrence T(n) <= 7T(n/7) + n, T(1) = 1. Guess #1: T(n) <= n*log_b(n). Oops - doesn't handle base case. Guess #2: T(n) <= n*log_b(n)+g(n), where g(1) >= 1. Assume true inductively. This means that T(n) <= 7*[(n/7)*log_b(n/7) + g(n/7)] + n. = n*log_b(n/7) + 7*g(n/7) + n. Now, set b=7, because log_7(n/7) = log_7(n)-1. So, T(n) <= n*log_7(n) - n + 7*g(n/7) + n Just need 7*g(n/7) <= g(n) and g(1) >= 1. Suggestions? g(n) = n works. So, this "guess" holds true inductively. Therefore, T(n) <= n*log_7(n) + n = O(n log n). Important to be careful. Here is a "proof" that the answer is O(n). See if you can tell where it goes wrong: Guess: T(n) <= c*n, where c >=1 to handle the base case. Assume true inductively. This means that can plug into the recurrence: T(n) <= 7*[cn/7] + n = cn + n = O(n). This is incorrect! 3. solving by building recursion tree Mergesort recurrence: do cn work, plus recurse on two problems of size n/2. problem size time spent add up row-wise n cn cn / \ n/2 cn/2 cn/2 cn / \ / \ n/4 cn/4 cn/4 cn/4 cn/4 cn . . . 1 c...................c cn log_2(n) levels, so result is Theta(n log n). - One more example before generalizing: let's do Karatsuba multiplication recurrence T(n) = 3T(n/2) + cn. Base case: T(1) = c. problem size time spent add up row-wise n cn cn / | \ n/2 cn/2 cn/2 cn/2 (3/2)cn /|\ /|\ /|\ n/4 cn/4 ...........cn/4 (9/4)cn ... Each time we go down a step, we multiply by 3 and divide by 2, and there are log_2(n) levels. So, we get a sum of: cn[1 + 3/2 + (3/2)^2 + ... + (3/2)^{log_2(n)}] Diversion into summations of geometric series: Consider any real r ^= 1. S_d = 1 + r + r^2 + + r^d. Can solve by considering r * S_d = r + r^2 + r^3 + + r^{d+1} and subtracting. Terms cancel, so (1-r)S_d = 1 r^{d+1}, i.e. S_d = (1-r^{d+1})/(1-r). When |r| < 1, we have lim_{d->infty} S_d = 1/(1-r). Back to the recurrence. We have that cn[1 + 3/2 + + (3/2)^{log_2(n)}] = cn((3/2)^{log_2 n} - 1)/(3/2 - 1) = Theta(n(3/2)^{log_2 n)). But n*(3/2)^(log_2 n) = 3^{log_2 n} = (2^{log_2 3})^{log_2 n} = n^{log_2 3} Thus T(n) = O(n^{log_2 3}) ********** "Master Formula" Now, let's generalize to: T(n) = a*T(n/b) + cn. where a >= 1, b > 1, c >= 1 are constants, and n is a nonnegative integer. [book does even more general case by replacing cn with f(n), and addressing integrality issues, on p.67. Students should take a look] We just get the same tree as before, but replacing 3 by a, 2 by b. So, we get a summation of: cn[1 + a/b + (a/b)^2 + (a/b)^3 + ... + (a/b)^depth] where depth = log_b(n). Case 1: What if a= n). So, ===> Theta(n). Case 2: What if a=b? all terms in sum are equal to 1, and there are 1 + log_b n terms. ===> Theta(n log n). Case 3: What if a>b? This is the case we just did with Karatsuba. Result is Theta(n*(a/b)^(log_b n)) = Theta(a^{log_b(n)}) = Theta( n^{log_b(a)} )