On Time Versus Input SizeHow to add 2 n-bit numbers.Slide 3Slide 4Slide 5Slide 6Slide 7Time complexity of grade school additionRoadblock ???Our GoalPowerPoint PresentationSlide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18How to multiply 2 n-bit numbers.Slide 20Grade School Addition: Linear time Grade School Multiplication: Quadratic timeSlide 22Grade School Multiplication: Quadratic timeTime Versus Input SizeHow much time does it take?What is T(n) ?Slide 27Slide 28Worst-case Time Versus Input SizeWhat is T(n)?Slide 31Slide 32Factoring The Number n By Trial DivisionSlide 34Slide 35Useful notation to discuss growth ratesSlide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44QuickiesNames For Some Growth RatesSlide 47Slide 48Binary SearchSome Big Ones2STACKlog*(n) = Inverse 2STACK(n) # of times you have to apply the log function to n to get it ito 1Slide 53Ackermann’s FunctionInverse AckermannSlide 56Slide 57Slide 58Slide 59Slide 60Time complexity of grade school multiplicationSlide 62Slide 63Slide 64Slide 65Any algorithm for addition must read all of the input bitsSlide 67Slide 68Grade School Addition: (n) time Furthermore, it is optimal Grade School Multiplication: (n2) timeSlide 70Slide 71Grade School Multiplication: (n2) time Kissing IntuitionOn Time Versus Input SizeGreat Theoretical Ideas In Computer ScienceSteven RudichCS 15-251 Spring 2004Lecture 15 March 2, 2004 Carnegie Mellon University# of bitstimeHow to add 2 n-bit numbers. ** ** ** ** ** ** ** ** ** ** ** +How to add 2 n-bit numbers. *** ** ** ** ** ** * ** ** ** ** ** +How to add 2 n-bit numbers. *** ** ** ** ** * ** * *** ** ** ** ** +How to add 2 n-bit numbers. *** ** ** ** * ** * *** * *** ** ** ** ** +How to add 2 n-bit numbers. *** ** ** * ** * *** * *** * *** ** ** ** ** +How to add 2 n-bit numbers. *** * *** * *** * *** * *** * *** * *** * *** * *** * *** *** * +* *Time complexity of grade school addition *** * *** * *** * *** * *** * *** * *** * *** * *** * *** +* * * *** T(n) = The amount of time grade school addition uses to add two n-bit numbersWhat do you mean by “time”?Roadblock ???A given algorithm will take different amounts of time on the same inputs depending on such factors as:–Processor speed–Instruction set–Disk speed–Brand of compilerOur GoalWe want to define TIME in a sense that transcends implementation details and allows us to make assertions about grade school addition in a very general way.Hold on! You just admitted that it makes no sense to measure the time, T(n), taken by the method of grade school addition since the time depends on the implementation details. We will have to speak of the time taken by a particular implementation, as opposed to the time taken by the method in the abstract.Don’t jump to conclusions!Your objections are serious, but not insurmountable. There is a very nice sense in which we can analyze grade school addition without ever having to worry about implementation details.Here is how it works . . .On any reasonable computer adding 3 bits and writing down the two bit answer can be done in constant time. Pick any particular computer A and define c to be the time it takes to perform on that computer. Total time to add two n-bit numbers using grade school addition: cn[c time for each of n columns]Implemented on another computer B the running time will be c’n where c’ is the time it takes to perform on that computer. Total time to add two n-bit numbers using grade school addition: c’n[c’ time for each of n columns]The fact that we get a line is invariant under changes of implementations. Different machines result in different slopes, but time grows linearly as input size increases. # of bits in numberstimeMachine A: cnMachine B: c’nThus we arrive at an implementation independent insight: Grade School Addition is a linear time algorithm.Determining the growth rate of the resource curve as the problem size increases is one of the fundamental ideas of computer science.I see! We can define away the details of the world that we do not wish to currently study, in order to recognize the similarities between seemingly different things.. AbstractionAbstraction: : Abstract away the inessential Abstract away the inessential features of a problem or solutionfeatures of a problem or solution=TIME vs INPUT SIZEFor any algorithm, define INPUT SIZE = # of bits to specify inputs,Define TIMEn = the worst-case amount of time used on inputs of size n.We Often Ask:What is the GROWTH RATE of Timen ?How to multiply 2 n-bit numbers.X* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *n2How to multiply 2 nHow to multiply 2 n--bit numbers.bit numbers.X* * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * ** * * * * * * ** * * * * * * ** * * * * * * ** * * * * * * ** * * * * * * ** * * * * * * ** * * * * * * * * * * * * * * *n2I get it! The total time is bounded by cn2.Grade School Addition: Linear timeGrade School Multiplication: Quadratic timeNo matter how dramatic the difference in the constants the quadratic curve will eventually dominate the linear curve# of bits in numberstimeOk, so…How much time does it take to square the number n using grade school multiplication?Grade School Multiplication:Quadratic time(log n)2 time to square the number n# of bits in numberstimeTime Versus Input SizeInput size is measured in bits, unless we say otherwise.# of bits used to describe inputtimeHow much time does it take?Nursery School Addition INPUT: Two n-bit numbers, a and bOUTPUT: a + bStart at a and add 1, b timesT(n) = ?What is T(n) ?Nursery School Addition INPUT: Two n-bit numbers, a and bOUTPUT: a + bStart at a and add 1, b timesIf b=000.0000, then NSA takes almost no time. If b = 111111.11, then NSA takes c n2n time.What is T(n) ?Nursery School Addition INPUT: Two n-bit numbers, a and bOUTPUT: a + bStart at a and add 1, b timesWorst case time is c n2n Exponential!Worst-case Time T(n) for algorithm A means that we define a measure of input size n, and we define T(n) = MAXall permissible inputs X of size n running time of algorithm A on X.Worst-case Time Versus Input SizeWorst Case Time Complexity# of bits used to describe
View Full Document
Unlocking...