Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2014:journals:alyssa:chapter2.2 [2014/01/20 18:06] – hardnetta | courses:cs211:winter2014:journals:alyssa:chapter2.2 [2014/01/20 18:37] (current) – hardnetta | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| + | ====== Chapter 2.2: Asymptotic Order of Growth ====== | ||
| + | |||
| + | |||
| If we can express an algorithm’s worst-case running time on inputs of size n as growing at a rate that is proportional to some function f(n), then that function becomes a bound on the running time of the algorithm. Counting the number of steps an algorithm executes is essentially meaningless both because we will often be using pseudo-code and because we want to classify broad classes of algorithms so we need a more general way of determining running time. So, we want to express the growth rate of running times in a way that is insensitive to constant factors and low-order terms. | If we can express an algorithm’s worst-case running time on inputs of size n as growing at a rate that is proportional to some function f(n), then that function becomes a bound on the running time of the algorithm. Counting the number of steps an algorithm executes is essentially meaningless both because we will often be using pseudo-code and because we want to classify broad classes of algorithms so we need a more general way of determining running time. So, we want to express the growth rate of running times in a way that is insensitive to constant factors and low-order terms. | ||
