Great Theoretical Ideas In Computer Science Steven Rudich CS 15 251 Lecture 15 March 2 2004 Carnegie Mellon University On Time Versus Input Size t i m e of bits Spring 2004 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 Time complexity of grade school addition T n The amount of time grade school addition uses to add two n bit numbers What 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 compiler Our Goal We 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 t i m e in h ac M e n c A c n B hine c a M of bits in numbers 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 Thus 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 Abstraction Abstract away the inessential features of a problem or solution 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 TIME vs INPUT SIZE For 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 n2 X How to multiply 2 n bit numbers X n2 I get it The total time is bounded by cn2 Grade School Addition Linear time Grade School Multiplication Quadratic time t i m e of bits in numbers No matter how dramatic the difference in the constants the quadratic curve will eventually dominate the linear curve Ok so 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 log n 2 time to square the number n Time Versus Input Size t i m e of bits used to describe input 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 add 1 b times T n What is T n Nursery School Addition INPUT Two n bit numbers a and b OUTPUT a b Start at a and add 1 b times If 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 b OUTPUT a b Start at a and add 1 b times Worst 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 Size t i m e of bits used to describe input Worst Case Time Complexity What is T n Kindergarden Multiplication INPUT Two n bit numbers a and b OUTPUT a b Start at a and add a b 1 times We always pick the WORST CASE for the input size n Thus T n c n2n Exponential Thus Nursery School adding and 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 Multiplication is efficient what about reverse multiplication Let s define FACTORING n to 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 O n logn 2 time if division is O logn 2 On input n trial factoring uses O n logn 2 time Is that efficient No The input length is log n Let k log n In terms of k we are using 2k 2 k2 time The time is EXPONENTIAL in the input length We know methods of FACTORING that are sub exponential about 2cube root of k but nothing efficient Useful 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 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 Useful notation to discuss growth rates 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 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 Useful notation to discuss growth rates For any monotonic …
View Full Document
Unlocking...