Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:cs211:winter2014:journals:alyssa:chapter2.2 [2014/01/20 18:06] – created 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. | ||
| Line 11: | Line 14: | ||
| If f = O(g) and g = O(h), then f = O(h) | If f = O(g) and g = O(h), then f = O(h) | ||
| If f = Ω(g) and g = Ω(h), then f = Ω(h) | If f = Ω(g) and g = Ω(h), then f = Ω(h) | ||
| + | |||
| * Sums of functions: if we have an asymptotic upper bound that applies to each of the two functions f and g, then it applies to their sum | * Sums of functions: if we have an asymptotic upper bound that applies to each of the two functions f and g, then it applies to their sum | ||
