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
Running Time of 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 0.000003 sec is
used in all cases
For a linear program, this term is still significant for
moderate input sizes