22023, 140 PM [igor Arateis Algorithm Analysis Computer Science isn't just about programming, there's some real science involved. Among the many things scientists do is analysis. Algorithms can be analyzed. Let's see how. CONTEN Introduction * Measuring Time + Time Complexity Classes Comparison Asymptotic Analysis * The Effects of Increasing Input Size + The Effects of a Faster Computer + Further Study + Summary Introduction Itis important to be able to measure, or at least make educated statements about, the space and time complexity of an algorithm. This will allow you to compare the merits of two alternative approaches to a problem you need to solve, and also to determine whether a proposed solution will meet required resource constraints before you invest money and time coding. Analysis is done before coding. Profiling (a.k.a. benchmarking ) is done after the code is written, ALGORITHMS BY COMPLEXITY MORE ComPLEX ———> LEFIPAD QUICKSORT GIT = SELF GOOGLE ‘SPRALILING EXCEL SPREADSHEET MERGE DRIVNG SEARCH BUILT UP OVER 2D YEARS BY A CAR GACKEND CHURCH GROUP IN NEBRASKA TO COORDINATE THEIR, SCHEDULING: Measuring Time psi imu. edurayhotestalganayss! 98223,140 PM Age Artis ‘The absolute running time of an algorithm cannot be predicted, since this depends on the programming language used to implement the algorithm, the computer the program runs on, other programs running at the same time, the quality of the operating system, and many other factors. We need a machine- independent notion of an algorithm's running time. ‘The current state-of-the-art in analysis is finding a measure of an algorithm's relative running time, as a function of how many items there are in the input, i.e., the number of symbols required to reasonably encode the input, which we call n. The n could be: * The number of items in a container * The length of a string or file + The degree of a polynomial + The number of digits (or bits) in an integer ‘The first three only make sense when each of the elements (items, characters, coefficients/exponents) have a bounded-size. For example: if all items are 64-bit integers, then the number of items can be used for n, but if numeric values are unbounded, you have to count bits! This is so important it is worth restating If your collection contains numbers that are fixed in size, like Java's ints or doubles, then the number of items is a reasonable input measure. But for unbounded values, like Java's BigInteger or Bigdecinal, then the numbers themselves are collections and the number of bits in the number becomes part of the problem input size. We count the number of abstract operations as a function of n. Abstract operations are also called steps Example: Printing each element of an array for (oan Systm ot rie loGOD Here n = a. length (provided we know that all of the items in the array have a fixed size, which is often the case). The abstract operation of interest here is the print. We print n times. The algorithm has n steps. So we say |T(n) = n What about the other operations? psi imu edurayhotesialganayss! 219ew, 140M Aigoritm arayeis Frankly, the prints are such big heavy operations that the increments and comparisons in the for-loop just dont really contribute anything substantial, so yeah, we really do ignore them. Example: Printing every other element of an array for (var 1 = 8; 4 € atenetg 44 2) spren.ot pre AGED} ‘Again we are assuming we live in a world in which n = a. Length. And again the abstract operation is n the print. We can see that|T'(n) = J | This can also be written T(n) Example: Getting the last element of an array retin [sles = Ms ‘iro! now NesuhERaentExeptiont): ‘One step, no matter how big the array is! Here n = a. length, and|T(n) = 1}. This is the best you can get. So good, Example: Finding the index of a given value in an array for (va sol Hae return Optional. of); ream options. soe) Here we need to introduce the B (best-case) and W (worst-case) functions: | B(n) = 1] and W(n) = n| (What about the average case? It's often difficult and sometimes impossible to compute an average case. You have to know something about the expected distributions of items.) psi imu. edurayhotestalganayss! ane22023, 140 PM [igor Arateis Example: Printing a Multiplication Table For the next few examples, let's assume n has been given to us. for (ar ens for (oe an Spsenoctoriei (ME, 6+ 9) Syren. orsnin0s The outer loop is executed n times. Inside this loop, we have n + 1 prints (n prints for the numbers and one for the printin). So[T'(n) = n(n + 1)], which we can also write] 7'(n) = n? + n|, The latter ‘expression looks good: we printed n” numbers and n newlines. Example: Printing a Triangle Let's count: 0: The first time through the loop (i = 0), we print one newline. The second time (i = 1), we do two prints (one star and one newine). The third time (i = 3) we perform three print operations. So in total, we print 1+ 2+ 3+ +--+ ntimes, or )>7_) 4. Perhaps you once learned how to make n(n +L closed forms for sums lke these. In our case, this is|T(n) = nes) | or perhaps better T(n) = pn? + 4n} Example: Halving If we keep halving a number, we don't go through an entire range. In fact, we finish really quickly: for (var i= rye psi imu. edurayhotestalganayss! ane220,140 grt Aras This is [TC [log, n] |. Halving leads to log,’s in the complexity functions, By the way, it is traditional in this line of analysis to take base-2 as the default. So when we write log n, we mean log, n. We also get the same logarithmic behavior not by halving, but by successively doubling a gap: for War Sway Gens tet span. orieln( Same complexity as before. Exercise: Perform a rigorous analysis to derive the complexity function. Example: An Interesting Nested Loop for (ar $=; Lee ng DDE Here the outer loop is done log n times and the inner loop is done n times, so] T'(n) = nlogn Example: Binary Search LOGS IN REAL LIFE! Given a sorted list, you can find a value in it by comparing the value against the middle value of the list. If the list is empty, you did not find it. I the value is equal to the middle value, you found it! Ifthe value is smaller than the middle value of the list, you can search the first have and never ever consider the second half. If larger, then you can search the second half without ever considering the first half. Let's find the 71. Start in the middle. The middle element is bigger so we search the right half. We continue as follows: 3e 12 15 21 28 29 30 31.35 38 39 41 43 45 48 51 52 [55] 57-58 7172 79 go 81 82 BB 89 90 91.92 1@ 12 15 21 28 29 36 31 35 38 39 41 43 45 43 51 52 55 57 5B 7173 79 80 Bi 88 89 90 91 92 93 95, 1@ 12 15 21 28 29 30 31 35 38 39 41 43 45 48 51 52 55 57 SB 71 88 89 90 91 92 93 95, 20 12 15 21 28 29 36 31.35 38 3941 43 45 48 52.52 55 57 BB] 21.73 79 80 81 82 88 89 50 91 92 93 95 psi imu. edurayhotestalganayss! 51922023, 140 PM [igor Arateis 1@ 12 15 21 28 29 3@ 31 35 38 39 41 43 45 4B 51 52 55 57 5: 73 79 80 81 82 88 89 98 91 92 93 95 Looks like we found it, We are halving our search space each time. And we do this at most log, times. Well it does get tricky because we aren't exactly halving the list, but in broad strokes that's perfectly reasonable. We are, after all, counting abstract operations. By the way, you might get lucky and the value you are looking for is right in the middle. This means we have | B(n) = 1] and] W(n) = log n|. (See, we're now starting to use the fact that 2 is the default base in computer science.) Example: Enumerating Subsets Logs are really cool. If you had one billion elements in your input, you need only 30 steps to solve your problem. If your input was all the atoms in the observable universe, you need less than 300 steps. Now let's flip things around, What if your algorithm required a billion steps to solve a problem of size 30, ‘or over a nonillion steps for inputs of size 100? This is what happens when T'(n) = 2" ‘The classic example of this is: given a set of n elements, there are 2" subsets. If you had to list each one: Then you would be computing all 2” subsets, and for each of these you print each of the n elements, so we have |T'(n) = n2” You might encounter the need for subset generation irl when encountering a problem for which there is essentially no better approach than to try all possible subsets of the input to see which one “works.” Example: Enumerating Permutations Worse than exponential is factorial, Given a set of n elements, there are m! permutations. If you had to list each permutation: Then you would be computing n! permutations, and for each of these you print each of the 7. elements, so we have|T'(n) = n-n! psi imu. edurayhotestalganayss! a922023, 140 PM [igor Arateis ‘You might encounter the need for permutation generation irl when encountering a problem for which there is essentially no better approach than to try all possible arrangements of the input to see which one “works.” Exercise: Read this blog post to get a sense of the magnitude of the number 52 factorial. Seriously, read it IMPORTANT: Developing Intuition The most important thing in your study of these time complexity functions or to get a sense of what each of these functions really mean. Here are crucial things you need to make sure you are starting to understand: When T(n) = n, we touch every element in the input When T(n) = log n, we don't have to touch every element, we rapidly narrow down the search space, generally by halving [When T(n) = 1, we do a single operation and the input size has no effect And there are more to come. Example: Multiplying two square matrices We now return to consideration of input sizes. for War 205 €r5 HH) for (va <5 Jef for (ear = 95 K€ o5 oe) = S100 * Ua DIL = ss Three nested loops, each done n times. So} T'(n) = n‘ While this is definitely the right function in terms of n, it might not be a fair measure of the complexity relative to the size of the input. Here n is the width of the matrices, not the actual number of elements in the input. The input size is the number of entries in the two matrices. If we say that the width of the matrices is n, then the input size is actually 2n” So to get things all correct here, we want 7 to be the number of matrix entries. If the matrices are square, the matrix width w is 4/37, or (0.5n)°* and the number of abstract operations to multiply the matrices psi imu. edurayhotestalganayss! m9zs, #0 PM Agari Arps is w* = ((0.5n)®5)3 = (0.5n)"5 = 0.353553n"5 That said, you will sometimes see people using the width for n. 1 Example: Addition Here’s another case where you should, in practice, be careful with the input size. If and y are primitive int values that each fit in a word of memory, any computer can add them in one step: |T(n) = 1|, Butif these are Biginteger values, then what matters is how many digits (or bits) there are in each value. Since we just have to add the digits in each place and propagate carries, we get T(n) =n] Time Complexity Classes Time to get real academic. We can group complexity functions by their “growth rates" (something we'll formalize in a minute). For example: Class T(n) Description Constant | 1 Fixed number of steps, regardless of input size Logarithmic | logn Number of steps proportional to log of input size Polynomial | n*, k > 1| Number of steps a polynomial of input size Exponential | c”, ¢ > 1 | Number of steps exponential of input size Those are four useful families to be sure, but we can define lots more: Class Description Constant 1 Doing a single task at most a fixed number of times. Example: retrieving the first element in a list. Inverse ‘Ackermann Iterated Log log*n. psi imu. edurayhotestalganayss! are22023, 140 PM gorithm Aratyeis Loglogarithmic | loglogn Logarithmic logn Breaking down a large problem by culling its size by some fraction. Example: Binary Search Polylogarithmic | (log n): e>1 Fractional Power | n°, O1 Quasipolynomial_| nls" Subexponential | 2", O1 | Often arises in brute-force search where you are looking for subsets of a collection of items that satisfy a condition. Factorial nt Often arises in brute-force search where you are looking for permutations of a collection of items that satisfy a condition. Neto-the-n n™ Double 2 Exponential ‘Ackerman ‘A(n) Runs Forever | 00 Comparison ‘To get a feel for the complexity classes consider a computer that performed one milion abstract operations per second: T(n) 10 20 50 100 1000 1000000 its Inu. eduraynotestalganayss! ato22023, 140 PM gorithm Aratyeis 1 1 1 ps ps bs us us us logn 3.32 4.32 5.64 6.64 9.97 19.9 us us us Lad us us n 10 20 50 100 1 1 us us bs bs msec second nlogn 33.2 86.4 282 664 9.97 19.9 bs bs bs bs msec seconds 100 400 25 10 1 11.57 bs bs msec msec second days 1000n? 100 400 25 10 167 317 msec msec seconds | seconds | minutes | years nd 1 8 125 1 16.7 317 msec msec msec | second | minutes __| centuries nies 24 420 1.08 224 25x10" | 4.23107" ms ms hours | days Ga Ga 1.01" 41.10 1.22 1.64 27 20.9 7.49x10°2 bs ps ps ps ms. Ga 0.000001 x 2” | 1.02 41.05 18.8 40.2 340x107” | 314x109 ns msec minutes | Ga Ga Ga an 1.02 1.08 35.7 | 4.02x10" | 3.40x10°"* | 3,14x10°71°°" ms seconds years | Gq Ga Ga n 3.63 ™ 9.64x10"" | 2.96x10'°° | 4.28%10°°* | — seconds | centuries Ga Ga Ga 2.78 3323 2,81%10" | 3.17%10""" | 3.471077" | — hours Ga Ga Ga Ga ca 5.70x10" | 2.14x10°°° |— _ _ _ Ga Ga By the way, Ga is a gigayear, or one billion years. There is something. Compare the 2" row with the 0.000001 - 2” row. The latter represents something running one million times faster than the former, but stil, even for an input of size 50, requires a run time in the thousands of centuries. its Inu. eduraynotestalganayss! 101922023, 140 PM [igor Arateis Asymptotic Analysis Since we are really measuring growth rates, we usually ignore: * all but the “largest” term, and * any constant multipliers so for example + An.0.4n5 + 3n3 + 253 behaves asymptotically like n® + An. 6.22nlogn + # behaves asymptotically like nlogn ‘The justification for doing this is: + The difference between 6n and 3n. isn't meaningful when looking at algorithms abstractly, since getting a computer that is twice as fast makes the former behave exactly like the latter. The underlying speed of the computer never matters in abstract analysis. Only the algorithm structure itself matters, + The difference between 2n. and 2n + 8 is insignificant as 7 gets larger and larger. + Ifyou are comparing the growth rates of, say, An. n3 and An. kn?, the former will always eventually overtake the latter no matter how big you make k. A leading constant can never make a function of a lower rank asymptotically worse than one from a higher rank. Exercise: Think deeply about all three of the above justifications. How can we formalize this? That is, how do we formalize things like “the set of all quadratic functions” or the “set of all inear functions” or “the set of all logarithmic functions"? Big-O: Asymptotic Upper Bounds Afunction f is in O(g) whenever there exist constants c and NV such that for every n > N, f(n) is bounded above by a constant times g(r). Formally’ O(g) =aey {f | 3eN.Vn > N.|f(n)| < elg(n)|} psi imu. edurayhotestalganayss! 922023, 140 PM, [igor Arateis o# gf) N This means that O(g) is the set of all functions for which g is an asymptotic upper bound of f. Examples + An.0.4n5 + 8n3 + 253 € O(An.n5) + An.6.22nlogn + * € O(An.nlogn) Notation By convention, people usually drop the lambdas when writing expressions involving Big-O, so you will see things like O(n?). Does this really let us throw away constant factors and small terms? Welllet's see why we should be able to, but only argue with one special case. (You can do the formal proof on your own.) Let's show that 7n4 + 2n? + n + 20 € O(n‘). We have to choose ¢ and N. Let's choose ¢ = 30 and N = 1. Sosince n > 1: |?n4 + 2n? +n + 20| < 7n* + 2n? +n+20 < Tn! + 2n4 +n‘ + 20n4 < 30n4 Too much technical detail? Want to review what this is all about? Here's a video: psi imu. edurayhotestalganayss! rae22023, 140 PM gorithm Aratyeis Big 0 Notation Is Big-O Useful? Big-O notation is really only most useful for large n. The suppression of low-order terms and leading constants is misleading for small n. Be careful of functions such as on? +1000n © 0,0001n5 + 10°n? © 10-42" + 1053 * Large constants on the more significant terms signify overhead, for example when comparing © 8nlogn and 0.01n? note that the former is worse until n gets up to 10,710. * Sedgewick writes "[Big-O analysis] must be considered the very first step in a progressive process of refining the analysis of an algorithm to reveal more details about its properties.” -0 is only an upperbound; it is not a tight upperbound. If an algorithm is in O(n”) itis also in O(n5), O(n), and O(2"). So it’s not really right to say that all complexity functions in O(2") are terrible, because that set properly includes the set O(1). Big-Q: Asymptotic Lower Bounds There is a Big-® notation for lower bounds. A function f is in 02(g) whenever there exist constants c and N such that for every n > N, f(n) is bounded below by a constant times g(n). (9) =aes {f | SEN. > N.|f(n)| > ela(n)]} psi imu. edurayhotestalganayss! 190223,140 PM Age Artis Lower bounds are useful because they say that an algorithm requires at least so much time, For ‘example, you can say that printing an array is O(2") because 2” really is an upper bound, it's just not a very tight one! But saying printing an array is 02(m) means it requires at least linear time which is more accurate. Of course just about everything is (1) Big-O When the lower and upper bounds are the same, we can use Big-Theta notation, (9) =aes {f | Jer ce N.Wn > N.cilg(n)| < |f(n)| < e2|9(n)|} Example: printing each element of an array is @(n). Now that’s usefull Exercise: Is it true to say @(g) = O(g) (9)? Why or why not? Most complexity functions that arise in practice are in Big-Theta of something. An example of a function that isn't in Big-© of anything is An. n? cosn. Exercise: Why isn't that function in Big-© of anything? Less-Common Complexity Functions There are also litte-ch and little-omega A(z) O(a) aes {F | Jim Ty) = 8 f(z) w() =aep {F | Jim Cy = oh Exercise: Find functions f and g such that f € O(g) differs from f € o(g) There's also the Soft-O: 0(g) =aey O(An. 9(n)(log 9(n))*) Since a log of something to a power is bounded above by that something to a power, we have O(a) ¢ O(An. g(n)'**) Determining Asymptotic Complexity psi imu. edurayhotestalganayss! se223,140 PM Age Artis Normally you can just look at a code fragment and immediately "see" that itis @(1), O(log n), O(n), (nog n), or whatever. But when you can't tell by inspection, you can write code to count operations for given input sizes, obtaining T'(m). Then you "guess" different values of f for which T' € @(f). To do this, generate values of 3h for lots of different fs and ns, looking for the f for which the ratio is nearly constant, Example: PrimeTimer.java | Snctine { eth that conutes all the pics Wp #9 9, and turns the inter of bic static lng Gm 9) ¢ we fs eaten]: = sow] = false, for (ar nie 8) 4 Geel) 0) = aise: olic static void yain(Steing) 225) ¢ sion Cn teen revingloe +P Teeyaan tei) for (var = ree; tre; 9 = LemHe8) ( = (cone) os “mat. so() Math oe (2.8) Paty star) / Math ee(2.0) syste. (8085. 9935.9985. 908.1208", 9, Chee Fo, oe Dy eine (5 * D2), (aru n°) Sova aorithns/Prinetinr.jovs Bj e.2m.cs.algoritins Prine psi imu edu'rayhotesialganayss! 11922023, 140 PM [igor Arateis Z(n) What we're seeing here is that the ratio 21) ig increasing, so the complexity is probably more than linear. The ratios wee and 7) are decreasing so those functions are probably upper bounds. But EEG Is also increasing, but the rate of increase seems to be slowing and who knows, might even converge. we could pet mat me compiexty € @(n log log n), put we snow reaty ao a tormal proor. The Effects of Increasing Input Size Suppressing leading constant factors hides implementation dependent details such as the speed of the computer which runs the algorithm. Stil, you can some observations even without the constant factors. For an algorithm of complexity | If the input size doubles, then the running time 1 stays the same logn increases by a constant n doubles its Inu. eduraynotestalganayss! swi9223,140 PM geri Artis rn quadruples nd increases eight fold an is left as an exercise for the reader The Effects of a Faster Computer Getting a faster computer allows to solve larger problem sets in a fixed amount of time, but for exponential time algorithms the improvement is pitifully small. For an Ifyou can solve a | Then ona500MHz | And on a supercomputer one , problem of this | PC you can solve a | thousand times faster than your algorithm of ° complex size on your | problem set of this | PC you can solve a problem set of pexity 100MHz PC size this size n 100 500 100000 nw 100 223 3162 oe 100 170 1000 an 100 102 109 More generally, T(n)| OMPresent | On a computer 100 | On a computer 1000) On a computer one Computer times faster times faster BILLION times faster n_|N 100N 1000N 1000000000N n? IN 10N 31.6N 31623N 3 IN 4.64N 10N 1000N n® IN 2.5N 3.9N 63N ar IN N+ 6.64 N+9.97 N+30 3" IN N+ 4.19 N+63 N+19 What if we had a computer so fast it could do ONE TRILLION operations per second? T(n)| 20 40 50 60 70 80 n& |3.2 [102 | 313 78 1.68 3.28 us| us us us msec msec its Inu. eduraynotestalganayss! a922023, 140 PM gorithm Aratyeis am 4.05 Ja. 138 [133 [374 383 msec | seconds| minutes | days | years centuries an 3s 47 227 1.3.x 10 |7.93 x 10" | 4.68 x 10°° msec | months | centuries] centuries | centuries _| centuries ‘As you can see, the gap between polynomial and exponential time is hugely significant. We can solve fairly large problem instances of high-order polynomial time algorithms on decent computers rather quickly, but for exponential ime algorithms, we can network together thousands of the world’s fastest ‘supercomputers and still be unable to deal with problem set sizes of over a few dozen. So the following terms have been used to characterize problems: Polynomial-time Algorithms | Exponential-time Algorithms Good Bad Easy Hard Tractable Intractable Further Study Here are some things not studied here that you will definitely want to pick up on later: * Other functions for complexity measures: log log n, n3, (logn)*, n!8", A(m,n), a(m,n), 2"/n, n?2", * Algorithms whose input size is quantified by more than one variable, as in graphs where n = the number of nodes and e = the number of edges and we find complexity measures such as O(e), Q(n?), O(n loge), O(n? loge), + Space Complexity + Formalized complexity classes: DLOG, NLOG, P, NP, PSPACE, and more (Don't miss the ‘Complexity Zoo) + Complexity measures for parallel, concurrent and distributed algorithms + Pessimal algorithms and simplexity analysis, + The Complexity of Songs Summary psi imu. edurayhotestalganayss! wie22023, 140 PM gorithm Arateis We've covered: EWhy we measure relative, not absolute, time [ithe idea of abstract operations WZ choosing n, the input size Easeveral examples of determining T(n) [the common (and some not-so-common) complexity classes WAsymptotic Analysis (O, ©, 2) [he effects of increasing input size [the effects of a faster computer psi imu. edurayhotestalganayss! sat9