1.204 Lecture 5 Algorithms: analysis, complexity Algorithms • Alggorithm: – Finite set of instructions that solves a given problem. – Characteristics: • Input. Zero or more quantities are supplied. • Output. At least one quantity is computed. • Definiteness. Each instruction is computable. • Finiteness. The algorithm terminates with the answer or by telling us no answer exists. • We will study common algorithms in engineering design dd i kiand decisiion-making – We focus on problem modeling and algorithm usage – Variations in problem formulation lead to greatly different algorithms • E.g., capital budgeting can be greedy (simple) or mixed integer programming (complex) 1t t ttAlgorithms: forms of analysis • How to devise an alggorithm • How to validate the algorithm is correct – Correctness proofs • How to analyze running time and space of algorithm – Complexity analysis: asymptotic, empirical, others • How to choose or modify an algorithm to solve a problem • How to implement and test an algorithm in a program – KKeep program codde shhort andd correspondd clloselly to allgorithi hm steps Analysis of algorithms • Time compplexityy of a ggiven alggorithm – How does time depend on problem size? – Does time depend on problem instance or details? – Is this the fastest algorithm? – How much does speed matter for this problem? • Space complexity – How much memory is required for a given problem size? • Assumptions on computer word size, processor – Fi d d/ i iFixed word/register size – Single or multi (grid, hypercube) processor • Solution quality – Exact or approximate/bounded – Guaranteed optimal or heuristic 2Methods of complexity analysis • Asymptotic analysis – Create recurrence relation and solve • This relates problem size of original problem to number and size of sub-problems solved – Different performance measures are of interest • Worst case (often easiest to analyze; need one ‘bad’ example) • Best case (often easy for same reason) • Data-specific case (usually difficult, but most useful) • Write implementation of algorithm (on paper) – Create table (on paper) of frequency and cost of steps – Sum upp the stepps;; relate them to pproblem size • Implement algorithm in Java – Count steps executed with counter variables, or use timer – Vary problem size and analyze the performance • These methods are all used – They vary in accuracy, generality, usefulness and ‘correctness’ – Similar approaches for probabilistic algorithms, parallel, etc. Asymptotic notation: upper bound O(..) • f(n)= O(g((g()) n)) if and only if() y – f(n) ≤ c * g(n) – where c > 0 – for all n > n0 • Example: – f(n)= 6n + 4√n – g(n)= n – c= 10 (not unique) – f(f(n))= c ** g((n)) whhen n= 11 0 – f(n) < g(n) when n > 1 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 n – Thus, f(n)= O(n) • O(..) is worst case (upper bound) notation for an algorithm’s complexity (running time) 5 10 15 20 25 30 35 40 45 f(n) c*g(n) 3Asymptotic notation: lower bound Ω(..) • f(n)= Ω(g((g(n)) if and onlyy if() )) – f(n) ≥ c * g(n) – where c > 0 – for all n > n0 • Example: – f(n)= 6n + 4√n – g(n)= n – c= 6 (again, not unique) – f(f(n))= c ** g((n)) whhen n= 00 – f(n) > g(n) when n > 0 n – Thus, f(n)= Ω(n) • Ω(..) is best case (lower bound) notation for an algorithm’s complexity (running time) 5 10 15 20 25 30 35 f(n) c*g(n) 0 0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 Asymptotic notation • Worst case or upper bound: O(..)Worst case or upper bound: O(..) – f(n)= O(g(n)) if f(n) ≤ c* g(n) • Best case or lower bound: Ω(..) – f(n)= Ω(g(n)) if f(n) ≥ c* g(n) • Composite bound: Θ(..) – f(n)= Θ(g(n)) if c1* g(n) ≤ f(n) ≤ c2* g(n) • AAverage or ttypiicall case nottatiti on iis lless fformall – We generally say “average case is O(n)”, for example 45Example performance of some common algorithmsAlgorithm Worst case Typical caseSimple greedy O(n) O(n)SortingO(n2)O(n lg n)Shortest pathsO(2n)O(n)Linear programmingO(2n)O(n)Dynamic programmingO(2n)O(2n)Dynamic programmingO(2)O(2)Branch-and-boundO(2n)O(2n)Linear programming simplex is O(2n), though these cases are pathologicalLinear programming interior point is O(Ln3.5), where L= bits in coefficientsShortest path label correcting algorithm is O(2n), though these cases are pathologicalShortest path label setting algorithm is O(a lg n), where a= number of arcs. Slow in practice.Running times on 1 GHz computerO( )O( l )O(n2)O(n3)O(n10)O(2n)nO(n)O(n lg n)O(n)O(n)O(n)O(2)10 .01 μs.03 μs .10 μs1 μs 10 s 1 μs50 .05 μs.28 μs2.5 μs 125 μs 3.1 y 13 d100 .10 μs.66 μs 10 μs 1 ms 3171 y1013 y1,000 1 μs10 μs1 ms1 s1013 y10283 y10,000 10 μs130 μs 100 ms 16.7 min1023 y100 000100 μs17ms10 s116d1033y100,000100 μs1.7 ms10 s11.6 d10y1,000,000 1 ms 20 ms 16.7 min 31.7 y1043 yAssumes one clock step per operation, which is optimisticco=Complexity analysis: recursive sum public class SumCountRec { static int count; public static double rSum(double[] a, int n) { unt++; count++; if (n <= 0) { count++; return 0.0; } else { count++; return rSum(a, n-1) + a[n-1]; } } } public static void main(String[] args) { count = 0; double[] a = { 1, 2, 3, 4, 5}; System.out.println("Sum is " + rSum(a, a.length)); System.out.println("Count is " + count); } } // We can convert any iterative program to recursive Complexity analysis: recurrence relations • For recursive sum: – T(n)= 2 if n= 0 – T(n)= 2 + T(n-1) if n> 0 • To solve for T(n) – T(n)= 2 + T(n-1) = 2 + 2 + T(n-2) = 2*2 + T(n-2) =n*2+T(0) n2 + T(0) = 2n + 2 Thus, T(n) = Θ(n) • Solving recurrence relations is a typical way to obtain asymptotic complexity results for algorithms – There is a master method that offers a cookbook approach to recurrence 61 32 0 1 54 76 2 ... • Max nodes on level i= 2i • Max nodes in tree of depth k= 2k+1-1 Binary tree: O(lg n) Level • This is full tree of deppth k • Each item in left subtree is smaller than parent • Each item in right subtree is larger than parent • It thus takes one step per level to search for an item • In a tree of n nodes, how may steps does it take to find an item? • Answer: O (lg n) • Approximately 2k nodes in k levels • Remember that logarithmic is the “inverse” of exponential Quicksort: O (n lg n)