15 251 Great Theoretical Ideas in Computer Science This is The Big Oh Lecture 21 March 31 2009 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 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 numbers What do we mean by time Our Goal We 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 compiler 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 i e 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 t i m e ac M n hi e n c M hine c a M c n M of bits in the numbers The fact that we get a line is invariant under changes of implementations Different machines result in different slopes but the time taken grows linearly as input size increases Thus we arrive at an implementation independent insight Grade School Addition is a linear time algorithm This process of abstracting away details and determining the rate of resource usage in terms of the problem size n is one of the fundamental ideas in computer science Time vs Input Size For any algorithm define Input Size of bits to specify its inputs Define TIMEn the worst case amount of time used by the algorithm on inputs of size n We often ask What is the growth rate of Timen How to multiply 2 n bit numbers X n2 How to multiply 2 n bit numbers X n2 The total time is bounded by 2 cn abstracting away the implementation details Grade School Addition Linear time Grade School Multiplication Quadratic time t i m e of bits in the numbers No matter how dramatic the difference in the constants the quadratic curve will eventually dominate the linear curve How much time does it take to square the number n using grade school multiplication Grade School Multiplication Quadratic time t i m e of bits in numbers c log n 2 time to square the number n Input size is measured in bits unless we say otherwise How much time does it take Nursery School Addition Input Two n bit numbers a and b Output a b Start at a and increment by 1 b times T n If b 000 0000 then NSA takes almost no time If b 1111 11111 then NSA takes cn2n time Worst Case Time Worst Case Time T n for algorithm A T n Max all permissible inputs X of size n Runtime A X Runtime A X Running time of algorithm A on input X What is T n Kindergarten Multiplication Input Two n bit numbers a and b Output a b Start with a and add a b 1 times Remember we always pick the WORST CASE input for the input size n Thus T n cn2n Thus Nursery School addition and Kindergarten multiplication are exponential time 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 Division Trial division up to N for k 2 to N do if k N then return N has a non trivial factor k return N is prime c N logN 2 time if division is c logN 2 time Is this efficient No The input length n log N Hence we re using c 2n 2 n2 time Can we do better We know of methods for FACTORING that are sub exponential about 2n1 3 time but nothing efficient Notation to Discuss Growth Rates For any monotonic function f from the positive integers to the positive integers we say f O n or f is O n If some constant times n eventually dominates f Formally there exists a constant c such that for all sufficiently large n f n cn f O n means that there is a line that can be drawn that stays above f from some point on t i m e of bits in numbers Other Useful Notation For any monotonic function f from the positive integers to the positive integers we say f n or f is n If f eventually dominates some constant times n Formally there exists a constant c such that for all sufficiently large n f n cn f n means that there is a line that can be drawn that stays below f from some point on t i m e of bits in numbers Yet More Useful Notation For any monotonic function f from the positive integers to the positive integers we say f n or f is n if f O n and f n f n means that f can be sandwiched between two lines from some point on t i m e of bits in numbers Notation to Discuss Growth Rates For any two monotonic functions f and g from the positive integers to the positive integers we say f O g or f is O g If some constant times g eventually dominates f Formally there exists a constant c such that for all sufficiently large n f n c g n f O g means that there is some constant c such that c g n stays above f n from some point on 1 5g t i m e f of bits in numbers g Other Useful Notation For any two monotonic functions f and g from the positive integers to the positive integers we say f g or f is g If f eventually dominates some constant times g Formally there exists a constant c such that for all sufficiently large n f n c g n Yet More Useful Notation For any two monotonic functions f and g from the positive integers to the positive integers we say f g or f is g If f O g …
View Full Document
Unlocking...