Concept of Basic Time ComplexityProblem instancesInstance SizeSize ExamplesExceptions: Number problemsExample 1: additionExample 2: FactorialEfficiencyExample: Sequential searchTime AnalysisSlide 11Time Analysis for Sequential searchSlide 13Worse case time analysisWorst case time analysisEvaluation of running time through experimentsRequirements for time complexity analysisIndependence RequirementA Priori RequirementLarge Instance RequirementGrowth Rate Classes RequirementGrowth rate classesInstruction countsComparing an nlogn to an n2 algorithmWho sorts a million numbers faster?Who is faster sorting 50 items?Insertion sortExample: Binary search (Recursive)Concept of Basic Time Complexity•Problem size (Input size)•Time complexity analysisProblem 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)(1, 2, 3, 4, 1000, 27)Instance Size•Formally: Size = number of (binary) bits needed to represent the instance in a computer.•We will usually be much less formal•For sorting 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 nSize Examples•Search and sort –Size = n number of records in the list. For search ignore search key•Graphs problems –Size = (|V| + |E|) –|V|: number of nodes–|E|: number of edges•Matrix problems –Size = r*c –r: number of rows –c: number of columnsExceptions: Number problems•Problems where input numbers can become increasingly large.•Examples:–Factorial of 10, 106, 1015–Operations (e.g., add and multiplication) of large numbers where a number is expressed using several words –For these problems we should use the formal definitionExample 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 = 5760001Example 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* 1030Efficiency•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 they need. •The time required by an algorithm depends on the instance size and its dataExample: Sequential search•Problem: Find a search key in a list of records •Algorithm: Sequential search–Main idea: Compare search key to all keys until a match is found or list is exhausted•Time depends on the size of the list n and the data stored in a listTime 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 sizeTime Analysis•If the best, worst and average “times” of some algorithms are identical, we have every case time analysis. e.g., array addition, matrix multiplication, etc.•Usually, the best, worst and average time of a algorithm are different.Time Analysis for Sequential search•Worst-case: if the search key x is the last item in the array or if x is not in the array. W(n) = n•Best-case: if x is matched with the first key in array S, which means x=S[1], regardless of array size n B(n) = 1Time Analysis for Sequential search•Average-case: If the probability that x is in the kth array slot is 1/n: 212)1(11111)()(nnnnnknnnkkknAQuestion: What is A(n) if x could be outside the array?Worse case time analysis•Most commonly used time complexity analysis•Because:–Easier to compute than average case; No knowledge on the probability of occurrence of instances needed.–Maximum time needed as a function of instance size. –More useful than the best case; Important for critical mission and real time problems.Worst case time analysis•Drawbacks of comparing algorithms based on their worst case time: - An algorithm could be superior in average than another, although the worst case time complexity is not superior. - For some algorithms a worst case instance is very unlikely to occur in practice.Evaluation of running time through experiments•Algorithm must be fully implemented•To compare run time we need to use the same hardware and software environments •Different coding style of different individuals’Requirements for time complexity analysis•Independence •A priori•Large instances•Growth rate classesIndependence Requirement•Time analysis must be independent of:–The hardware of a computer–The programming language used for pseudo code–The programmer that wrote the codeA Priori Requirement•Analysis should be a priori •Derived for any algorithm expressed in high level description, or pseudo code.Large Instance Requirement•Algorithms running efficiently on small instances may run very slowly with large instance sizes•Analysis must capture algorithm behavior when problem instances are large–For example, linear search may not be efficient when the list size n = 1,000,000Growth Rate Classes Requirement •Time analysis must classify algorithms into:– Ordered classes so that all algorithms in a single class are considered to have the same efficiency.–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.Growth rate classes•Growth rate classes are derived from instruction counts•Time analysis partitions algorithms into general equivalence classes such as:–logarithmic,–linear, –quadratic, –cubic,–polynomial–exponential, etc.Instruction counts•Provide rough estimates of actual number of instructions executed•Depend on:–Language used to describe algorithm–Programmer’s style–Method used to derive count•Could be quite different from actual counts•Algorithm with count=2n, may not be faster than one with count=5n.Comparing an nlogn to an n2 algorithm•An nlogn algorithm is always more efficient for large instances•Pete is a programmer for a super computer. The computer executes 100 million instructions per second. His implementation of Insertion Sort requires