CS211 Spring 2002 Lecture 13: Asymptotic Complexity 3/4/2003 ------------------------------------------------------------------------------- 0) Announcements + Prelim 1 (T1) this week (see website for rooms) (bring ID) + review session this week (see website in Prelims) + A4 due 3/12 (see online material) + DIS schedule Overview + math review + algorithm analysis - machine view of time and space - approximate view of time and space + complexity analysis - space (asymptotic space complexity) - timing (asymptotic time complexity) + big Oh notation + recurrence relations (DS&SD: 18.5, App C; DS&A: 2.1.5) ------------------------------------------------------------------------------- 1) Math Review See mathreview.txt, DS&SD: pg 100, App. C) Why math? + want theoretical tool to analyze algorithms + the steps of an algorithm can be counted + counting means numbers... ------------------------------------------------------------------------------- 2) Algorithm Analysis Algorithm: + steps to solve a problem + supposedly independent of implementation Program: + implementation of an algorithm + specific language How to analyze an algorithm? (from DS&A) + running time + memory needed/used + correctness of output/results + clarity for a human + robustness/generality "Exact" analysis: + hardware (CPU, memory,...) + software (OS, lang, compiler,...) How we analyze: + "exact" analysis is too detailed + need other kinds of measures + focus on TIME and SPACE for algorithm - time: how many steps required? - space: how much memory needed? + we tend to focus on time, since memory is "cheap" ------------------------------------------------------------------------------- 2) Machine Model (see DS&A, CS212 notes) Stack Machine: + memory for stack ops, static area, registers, heap (!), program area + space: how much of the memory is needed + time: how quickly can the values be stored and retrieved JVM: + Java code compiled to BYTE CODE and stored in program area + byte code is of form INSTRUCTION VALUE + interpreter acts on each instruction one at a time + instructions store and retrieve values from areas of memory Runtime Performance for JVM: + some axioms: - tfetch: time required to fetch an operand is constant - tstore: time required to store a result is constant - top: time required to perform an ALU op is constant - tcall: time required to call a method is constant - treturn: time requited to return from a method is constant (see CS212 for the steps to take for methods) - tf(arg): time required to pass arg to method same as Tstore - t[.] : time required to calculate the address for a subscript (time to "find" a specific element) - tnew: time time to create an object is constant (does not include initialization of fields in object) + examples: y = y + 1 has 2tfetch + top + tstore (y, 1) (+) (y=...) y = a[i] has 3tfetch + t[.] + tstore (a,i,a[i]) (address) (y=...) Space Analysis of Machince Model: + Run "SaM" to see the stack grow and shrink + best and worst case: try not to run out of stack space! Time Analysis of Machine Model: + average running time - kind of complicated -- see DS&A - think of probability of getting certain inputs - see also DS&SD 5.1.2 and Table 5.1 + worst case - assume worse possible ordering of data or input + best case - assume best possible ordering of data or input ------------------------------------------------------------------------------- 3) Simplified Model of Computer Space: + each "chunk" required to store something has same number of bits + we're not going to do too much with this + timing analysis is more popular Time: + Some "basics" from ECE: - processor CLOCK: coordinates memory ops by generating time reference signal called CLOCK CYCLE or TICK - CLOCK SPEED: + how fast instructions execute + measured as CLOCK FREQUENCY: how many ticks per second (MHz or GHz) - instruction/tick? + depends on CPU, instruction set, instruction type + one instruction takes one tick, maybe more + architectures: CISC (PCs), RISC (Macs, Suns) - CLOCK PERIOD: + T = 1/frequency (unit of time/tick) + measured nano (or smaller) seconds - example) 2.4 GHz Gateway® E-6000 has -> clock speed: 2.4x10^9 tick/s clock speed and -> clock period: 4.17x10^(-10) (s/tick) (or just 0.417 ns) + Relating time from algorithm to "actual" clock period: - T for clock period - time for instruction to happen is proportional to T (see instr/tick) - each timing param tsomething = kT (k is an integer, k > 0) + Simplification: - express timing params in terms of T + how many "Ts" does an instruction take? 1 cycle? more? + can say T=1 since we express the "ts" in terms of T - let all "ks" = 1 - so, we assume each operation takes the same amount of time (1 cycle) + ALU: 1 cycle + Assign: 1 cycle [store value on LHS; ops on RHS counted separately] + Loop: (total iterations) * ( (# of ops)/(iteration) ) cycles + Method: (number of ops "inside" a method) cycles + Approximate total time for a program: count cycles! + example courtesy of DS&A: analyze programs for sum(x,i=0..n) - see geosum0.java - results in geosum1 and geosum2 results: - geosum1 (mult each term): (11/2)*n^2 + (47/2)*n + 24 - geosum2 (horner's rule): 13n+22 conclusions: - not algorithms are created the same! - some algorithms are better than others! + DS&SD notation and concepts: - TSmax(n): + count everything + max number of cycles - TAmax(n): + pick the "dominant" or "most important" operation and count that (called the ACTIVE OPERATION) + must be most frequent or with a constant of being more frequent + not the same as TSmax(n), but grows at same rate ------------------------------------------------------------------------------- 4) Recurrence/Recursive Relations (see DS&SD 18.5, App C.5 and DS&A Chap 2) + How to handle recursion and timing analysis? + RECURRENCE RELATION/RECURSIVE RELATION: - specify initial values: base case(s) - define remaining values as a function of previous values example from DS&A) factorial Code: int fact(int n) { if (n==0) return 1; else return n*fact(n-1); } Runtime: if n==0, T=5 (let t1=5) how? 3 for "n==0" + 1 for "return" + 1 for "1" if n>0, T=T(n-1) + 11 how? 3 for "n==0" + 1 for "return" + 1 for "n" + 1 for "*" + 1 for call to "fact" + 1 for "n" + 1 to store "n-1" + 1 for "-" + 1 for "1" + time to do NEXT call "fact(n-1)" { t1, n==0 rr: T(n) = { { T(n-1)+t2, n > 0 + Ways to solve recurrence rels: - primary approach: repeated substitution - see C.5.2 for other approach Try repeated subs for factorial: T(n) = T(n-1) + t2 = (T(n-2) + t2) + t2 = T(n-2) + 2t2 = (T(n-3) + t2) + t2 = T(n-3) + 3t2 ... Try to find a pattern.... it appears to be T(n)=T(n-k)+kt2 for 0<=k<=n Can prove this by induction. + These sorts of proofs will show up quite a bit in sorting algorithms and data structures ------------------------------------------------------------------------------- 5) Asymptotic Complexity (also "growth notation, asymptotic notation, Big Oh....") + How to compare algorithms? - find each T(n) equation - problem: they're not really that exact because of assumptions - need "worst-case" scenarios! + Example: Compare these: - geosum1 (mult each term): (11/2)*n^2 + (47/2)*n + 24 - geosum2 (horner's rule): 13n+22 - geosum3 (see DS&A): 19(floor(log[2](n+1))+1)+18 - see Fig2.3 in DS&A for plots or MATLAB: >> n=linspace(0,10,100); >> E1= (11/2)*n.^2 + (47/2)*n + 24; >> E2= 13*n+22; >> E3= 19*(floor(log2(n+1))+1)+18; >> plot(n,E1,n,E2,n,E3) observations: + geosum1 grows faster than geosum2 + geosum2 grows faster than geosum3 + for small values of n, geosum3 is actually worse in time than 1 and 2 conclusion: + need a measure that is accurate in the "larger" case + One measure: ASYMPTOTIC UPPER BOUND O(g(n)) = { f(n) | (c, n0) such that 0 <= f(n) <= cg(n) for all n >= n0 } | cg(n) | / __ f(n) Say f(n)=O(g(n)) (g(n) bounds f(n)) | / __-- if f(n) <= cg(n) for some n=n0 and c. | __/-- Needs witness pair: n0 and c | /| for n >= n0 and c >= 0, where n>=0 | / | |/ | | | +---+------------> n n0 O(g(n)) provides an ASYMPTOTIC UPPER BOUND. (not the tightest upper bound, though. See Theta(g) for that :-) + Why "asymptotic"? - Because we talk about the highest-order term, which is the asymptote that the runtime approaches, even if it isn't exactly what the runtime ends up being. - This may not seem "fair". For example, 2n+10 takes more time than n+1, but they have the same asymptotic complexity! Why? We always drop the constants and lower terms - ex) O((11/2)n^2 + (47/2)n + 22) = O(n^2) O(13n+20) = O(n) - Note: for a small number of steps, the lower terms and constants may dominate, but eventually the higher terms (which relate to number of comparisons and iterations) dominate + Why "complexity"? - Because we talk about the amount of work that must be done (how many steps must be performed.) Usually this is in terms of number of comparisons or number of swaps, for a searching or sorting algorithm. - Amount of work required = complexity of the problem. + Why "complexity classes"? - Class: classification of sets of bounding functions + Why is this important? 1. It allows us to compare two algorithms that solve the same problem and decide which one is more efficient. 2. It allows us to estimate approximately how long it might take to run a program on a specific input. - e.g. If I have an O(n^3) algorithm, and I give it an input with 300 items, it will take about 27,000,000 steps! If I know how many such steps my computer can do per second, I can figure out how long I'll have to wait for the program to finish. - Note that it's important to know what is being measured. Number of comparisons? Swaps? Additions? Divides? (ouch! Divide is VERY expensive!) + Example 1: f1(n)=(11/2)n^2 + (47/2)n + 22 is in O(n^3) so, f1(n) <= c * n^3 for some c > 0 and n >= n0 >= 0 we need to find a (c,n0)! (11/2)n^2 + (47/2)n + 22 <= cn^3 let c=1 n^3 - (11/2)n^2 - (47/2)n - 22 >= 0 n0 = 8.6 so, before n=8.6, f1(n) is higher than n^3. but afterwards, n^3 is higher, and is thus an upper bound. Note: you could actually make tight bounds is you said f1(n)=O(n^2) In general, for polynomials, with highest term n^m, f(n)=O(n^m) + Example 2: (From old prelim) Problem: Given f1(n)=O(g(n)) and f2(n)=O(g(n)) and h(n)=f1(n)+f2(n), is h(n)=O(g(n))? Justify formally using witness pairs (k,N). Solution: Yes Proof: Using givens and witness pairs (c1,n1) and (c2,n2): f1(n) <= c1*g(n) for all n > n1 f2(n) <= c2*g(n) for all n > n2 Let cs=c1+c2 and ns=max(n1,n2) to define witness pair (cs,ns). Add f1 and f2: f1(n)+f2(n) <= (c1+c2)*g(n) <= cs*g(n) This relation is true for all n > ns. Given our valid witness pair, h(n)=O(g(n)). + Example 3: Prove that for b > 1, log[b](n)=O(log[2](n)) log[b](n) = log[b](c) * log[c](n) so, log[b](n) = log[b](2) * log[2](n) since log[b](2) is a constant for a legal base b, that term drops -------------------------------------------------------------------------------