The main contents of the chapter consist of the following: Remaining part of maximum contiguous subsequence sum problem, general big-oh rule, running time of algorithm. | Lecture 17 Recap Remaining Part of Maximum Contiguous Subsequence Sum Problem General Big-Oh Rule Big-Oh Big-Omega Big-Theta Little-Oh Running Time of Algorithm Running Time of Cubic Algorithm Assume that the running time is reasonably approximated by T(N) = cConsequently, T(10N) =c Mathematical manipulation yields Thus the running time of a cubic program increases by a factor of 1000 when the amount of input is increased by a factor of 10 This relationship is roughly confirmed by the increase in running time from N = 100 to 1000 We do not expect an exact answer-just a reasonable approximation We would also expect that for N = 10,000, the running time would increase another 1000- fold The result would be that a cubic algorithm requires roughly 35 minutes of computation time In general, if the amount of input increases by a factor of f, the cubic algorithm's running time increases by a factor of Running Time of Quadratic Algorithm Assume that T(N) = c. It follows that T(1ON)=c. When . | Lecture 17 Recap Remaining Part of Maximum Contiguous Subsequence Sum Problem General Big-Oh Rule Big-Oh Big-Omega Big-Theta Little-Oh Running Time of Algorithm Running Time of Cubic Algorithm Assume that the running time is reasonably approximated by T(N) = cConsequently, T(10N) =c Mathematical manipulation yields Thus the running time of a cubic program increases by a factor of 1000 when the amount of input is increased by a factor of 10 This relationship is roughly confirmed by the increase in running time from N = 100 to 1000 We do not expect an exact answer-just a reasonable approximation We would also expect that for N = 10,000, the running time would increase another 1000- fold The result would be that a cubic algorithm requires roughly 35 minutes of computation time In general, if the amount of input increases by a factor of f, the cubic algorithm's running time increases by a factor of Running Time of Quadratic Algorithm Assume that T(N) = c. It follows that T(1ON)=c. When we expand, we obtain So when the input size increases by a factor of 10, the running time of a quadratic program increases by a factor of approximately 100 In general, an -fold increase in input size yields an -fold increase in running time for a quadratic algorithm Running Time of Linear Algorithm A similar calculation shows that a 10-fold increase in input size results in a 10-fold increase in running time This relationship has been confirmed experimentally For a linear program the term sufficiently large means a somewhat higher input size than for the other programs The reason is that of the overhead of sec is used in all cases For a linear program, this term is still significant for moderate input sizes 5 Running Time of Logarithmic Terms When an O(N log N) algorithm is presented with 10 times as much input, the running time increases by a factor slightly larger than 10. Specifically, we have T(10N)= c(10N)log(10N) When we expand, we obtain T(10N) = 10cN log (10N) = 10cN .
