On Time Versus Input SizeCarnegie Mellon UniversityMarch 15, 2005Lecture 17CS 15-251 Spring 2005Anupam GuptaGreat Theoretical Ideas In Computer Science# 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.*** * *** * *** * *** * *** * *** * *** * *** * *** * *** ****+* * “Grade school addition”Time complexity of grade school addition+T(n) = amount of time grade school addition uses to add two n-bit numbersWhat do you mean by “time”?* * * * * * * * * ** * * * * * * * * ** * * * * * * * * ** * * * * * * * * * *Our GoalWe want to define “time” in a way that transcends implementation details and allows us to make assertions about grade school addition in a very general yet useful way.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 compilerHold on! The goal was to measure the time T(n) taken by the method of grade school addition without depending on the implementation details. But you agree that T(n) doesdepend on the implementation!We can only speak of the time taken by any particular implementation, as opposed to the time taken by the method in the abstract.Your objections are serious, Bonzo, but they are not insurmountable. There is a very nice sense in which we can analyze grade school addition without 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 M 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]On another computer M’, the time to perform may be c’.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 the numberstimeMachine M: cnMachine M’: c’nThus we arrive at an implementation independent insight: Grade School Addition is a linear time algorithm.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 aw ay the inessential Abstract aw ay the inessential features of a problem or solutionfeatures of a problem or solution=Exactly, Bonzo!This process of abstracting away details and determining the rate of resource usagein terms of the problem size nis one of the fundamental ideas in computer science.Time vs Input SizeFor any algorithm, define Input Size = # of bits to specify its inputs.Define TIMEn= the worst-case amount of time used on inputs of size nWe 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 num bers.bit num bers.X* * * * * * * * * * * * * * * * * * * * * * * ** * * * * * * ** * * * * * * ** * * * * * * ** * * * * * * ** * * * * * * ** * * * * * * ** * * * * * * ** * * * * * * * * * * * * * * *n2I get it!The total time is bounded by cn2(abstracting away the implementation details).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 the numberstimeOk, so…How much time does it take to square the number n using grade school multiplication?Grade School Multiplication:Quadratic timec(log n)2time 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 AdditionInput: Two n-bit numbers, a and bOutput: a + bStart at a and increment (by 1) b timesT(n) = ?How much time does it take?Nursery School AdditionInput: Two n-bit numbers, a and bOutput: a + bStart at a and increment (by 1) b timesT(n) = ?If b = 000…0000, then NSA takes almost no time.If b = 1111…11111, then NSA takes c n2ntime.Exponential Worst Case time !!Worst Case TimeWorst Case Time T(n) for algorithm A:T(n) = Max[all permissible inputs X of size n](Running time of algorithm A on input X).Worst-case Time Versus Input SizeWorst Case Time Complexity# of bits used to describe inputtimeWhat is T(n)?Kindergarden MultiplicationInput: Two n-bit numbers, a and bOutput: a * bStart with a and add a, b-1 timesRemember, we always pick the WORST CASE input for the input size n. Thus, T(n) = c n2nExponential Worst Case time !!Thus, Nursery School adding and multiplication are exponentialtime. They scale HORRIBLY as input size grows.Grade school methods scale polynomially: just linear and quadratic. Thus, we can add and multiply fairly large numbers.If T(n) is not polynomial, the algorithm is not efficient: the run time scales too poorly with the input size.This will be the yardstick with which we will measure “efficiency”.Multiplication is efficient, what about “reverse multiplication”?Let’s define FACTORING(N) to be any method to produce a non-trivial factor of N, or to assert that N is prime.Factoring The Number N By Trial DivisionTrial division up to √Nfork= 2 to √Ndoifk | Nthenreturn “Nhas a non-trivial factor k”return “N is prime”c √N (logN)2time if division is c (logN)2 timeOn input On input NN, trial factoring uses , trial factoring uses c√N (logN)2time. Is this efficient?No! The input lengthNo! The input lengthn = log N.n = log N.Hence we’re using Hence we’re using c 2c 2n/2n/2nn22time.time.The time is The time is EXPONENTIALEXPONENTIALin in the input length the input length nn..Can we do better?We know of methods for FACTORING that are sub-exponential (about time) but nothing efficient.2n1/3Useful notation to discuss growth ratesFor
View Full Document
Unlocking...