This class:Problem instancesInstance SizeSize ExamplesNumber problemsExample 1: additionExample 2: FactorialEfficiencyExample: Sequential searchTime AnalysisSlide 11Worse case time analysisWorst case time analysisTime Analysis Using ExperimentsRequirements for time analysisIndependence RequirementA Priori RequirementLarge Instance RequirementGrowth Rate Classes RequirementThe classesInstruction countsComparing an nlogn to an n2 algorithmWho is faster sorting a million numbers?Who is faster sorting 50 items?Average case analysisCommonly used methodCommonly used method (Cont.)Average Case for Sequential SearchCase 1: Search Key in ListSlide 30Case 2: Search key in list with probability qSlide 32Search key in list with probability q=1/201/14/19 cs333/Cutler/Analysis 1This class:•Problem size•A-priori analysis•Average case analysis01/14/19 cs333/Cutler/Analysis 2Problem instances•An instance is the actual data for which the problem needs to be solved. •In this class we use the terms instance and input interchangeably.•Problem: Sort list of records.Instances: (1, 10, 5) (20, -40)(1, 2,3,4, 1000, -27)01/14/19 cs333/Cutler/Analysis 3Instance Size•Formally: Size = number of (binary) bits needed to represent the instance on a computer.•We will usually be much less formal•For sort we assume that the size of a record is a constant number of bits c•Formally the size of an input with n records is nc, we use n01/14/19 cs333/Cutler/Analysis 4Size Examples•Search and sort: Size = n number of records in the list. For search ignore search key•Graphs problems: Size = (|V| + |E|) number nodes |V| plus number edges in graph |E|.•Matrix problems: Size = r*c number of rows r multiplied by number of columns c01/14/19 cs333/Cutler/Analysis 5Number problems•Problems where input numbers can become increasingly large.•Examples:–Factorial of 10, 106, 1015–Fibonacci–Multiplying, adding, dividing•For these problems we should use the formal definition01/14/19 cs333/Cutler/Analysis 6Example 1: addition•Add two n-word numbers •Algorithm uses n word additions•Size = n and algorithm is O(n)011101010111 7*82+5*8+7 = 495000100100001 1*82+2*8+1 = 81+000100000000 1*83+1*82 = 576000101/14/19 cs333/Cutler/Analysis 7Example 2: Factorial•Compute factorial of an n bit number v. Its value is•2n - 1  v <2n•v! = v * v-1 *… * 3 * 2 *1•Algorithm does O(v) multiplications•Size of input = n•Example:–n = 100 bits (first bit is 1)–299 v <2100–v > 0.6* 1030•How many multiplications are needed?01/14/19 cs333/Cutler/Analysis 8Efficiency•The efficiency of an algorithm depends on the quantity of resources it requires•Usually we compare algorithms based on their time–Sometimes also based on the space resources they need. •The time required by an algorithm depends on the instance size, and its data01/14/19 cs333/Cutler/Analysis 9Example: Sequential search•Problem: Find a search key in a list of records •Algorithm: Sequential search•Main idea: Compare search key to all keys until– match, or–list is exhausted.•Time depends on the size of the list n, and on the data stored in a list.01/14/19 cs333/Cutler/Analysis 10Time Analysis•Best Case: The smallest amount of time needed to run any instance of a given size•Worst Case: The largest amount of time needed to run any instance of a given size•Average Case: the expected time required by an instance of a given size01/14/19 cs333/Cutler/Analysis 11Time Analysis•The best, worst and average “times” of some algorithms are identical•In this case we have every case time analysis. •Often they are different•Insertion sort has linear best case growth rate, and quadraticworst case growth rate.01/14/19 cs333/Cutler/Analysis 12Worse case time analysis•Commonly, we do only worst case analysis. •Reasons are:– Easier to compute than average case–More useful than best case.–No knowledge on the probability of occurrence of instances needed.–Gives maximum "time" needed as a function of instance size. –Important for critical mission, and real time problems.01/14/19 cs333/Cutler/Analysis 13Worst case time analysis•Drawbacks of comparing algorithms based on their worst case time:•We may not realize that an algorithm is superior on the average than another with a lower worst case time. •For some algorithms a worst case instance is very unlikely to occur in practice.01/14/19 cs333/Cutler/Analysis 14Time Analysis Using Experiments•Algorithm must be fully implemented.•Run time for chosen set of inputs and input sizes, may not be indicative of the run time for other sets of inputs and input sizes. •To compare run time we need to use the same hardware and software environments. •There may be differences because of the writing style of different individuals.01/14/19 cs333/Cutler/Analysis 15Requirements for time analysis•Independence •A priori•Large instances•Growth rate classes01/14/19 cs333/Cutler/Analysis 16Independence Requirement•Time analysis must be independent of:•The hardware of a computer,•The programming language used for pseudo code•The programmer that wrote the code.01/14/19 cs333/Cutler/Analysis 17A Priori Requirement•Analysis should be a priori •Derived for any algorithm expressed in high level description, or pseudo code.01/14/19 cs333/Cutler/Analysis 18Large Instance Requirement•Commonly algorithms run efficiently on small instances •May run very slowly with large instance sizes•Analysis must capture algorithm behavior when problem instances are large•Ignore behavior for small sizes01/14/19 cs333/Cutler/Analysis 19Growth Rate Classes Requirement •Time analysis should partition algorithms into:– ordered classes so that all algorithms in a single class are considered to have the same efficiency, and–if class A “is better than“ class B then all algorithms that belong to A are considered more efficient than all algorithms in class B.01/14/19 cs333/Cutler/Analysis 20The classes•Time analysis partitions algorithms into general equivalence classes such as:– logarithmic,– linear, –quadratic, –cubic,–polynomial– exponential, etc.•Reason for this kind of classification–Growth rate classes are derived from instruction counts01/14/19 cs333/Cutler/Analysis 21Instruction counts•Provide rough estimates of actual number of instructions executed•Depend on:– Language used to describe algorithm–Programmer style–Method used