[[courses:cs211:winter2018:journals:boyese:chapter2]]
Trace:
Show page
Recent ChangesSitemap

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
courses:cs211:winter2018:journals:boyese:chapter2 [2018/02/05 20:31] – [Section 2.3 : Implementing the Stable Matching Algorithm Using Lists and Arrays] boyesecourses:cs211:winter2018:journals:boyese:chapter2 [2018/02/05 20:31] (current) – [Section 2.2 : Asymptotic Order of Growth] boyese
Line 12: Line 12:
 In the previous section, we defined efficiency based on an algorithm's worst-case running time on inputs of size n which grows at a rate that is at most proportional to some function f(n). Thus, f(n) is a bound on the running time of the algorithm. In this section, we seek to express the growth rate of running times and other functions in a way that is insensitive to constant factors and low-order terms.\\  In the previous section, we defined efficiency based on an algorithm's worst-case running time on inputs of size n which grows at a rate that is at most proportional to some function f(n). Thus, f(n) is a bound on the running time of the algorithm. In this section, we seek to express the growth rate of running times and other functions in a way that is insensitive to constant factors and low-order terms.\\ 
 \\  \\ 
-**Asymptotic Upper Bounds**\\ +===Asymptotic Upper Bounds=== 
 Let T(n) be a function. Given some other function f(n), we say that T(n) is O(f(n)) if for sufficiently large n, the function T(n) is bounded above by a constant multiple of f(n), or T(n) = O(f(n)). Specifically, T(n) is O(f(n)) if there exist constants c > 0 and n<sub>0</sub> ≥ 0 so that for all n ≥ n<sub>0</sub>, we have T(n) ≤ c⋅f(n). In this case, we will say that T is asymptotically upper-bounded by f.\\  Let T(n) be a function. Given some other function f(n), we say that T(n) is O(f(n)) if for sufficiently large n, the function T(n) is bounded above by a constant multiple of f(n), or T(n) = O(f(n)). Specifically, T(n) is O(f(n)) if there exist constants c > 0 and n<sub>0</sub> ≥ 0 so that for all n ≥ n<sub>0</sub>, we have T(n) ≤ c⋅f(n). In this case, we will say that T is asymptotically upper-bounded by f.\\ 
 \\  \\ 
Line 18: Line 18:
 Consider an algorithm whose running time has the form T(n) = pn<sup>2</sup> + qn + r for positive constants p, q, and r. We’d like to claim that any such function is O(n<sup>2</sup>). To see why, we notice that for all n ≥ 1, we have qn ≤ qn<sup>2</sup>, and r ≤ rn<sup>2</sup>. So we can write T(n) = pn<sup>2</sup> + qn + r ≤ pn<sup>2</sup> + qn<sup>2</sup> + rn<sup>2</sup> = (p + q + r)n<sup>2</sup> for all n ≥ 1. This inequality is exactly what the definition of O(⋅) requires: T(n) ≤ cn<sup>2</sup>, where c = p + q + r.\\  Consider an algorithm whose running time has the form T(n) = pn<sup>2</sup> + qn + r for positive constants p, q, and r. We’d like to claim that any such function is O(n<sup>2</sup>). To see why, we notice that for all n ≥ 1, we have qn ≤ qn<sup>2</sup>, and r ≤ rn<sup>2</sup>. So we can write T(n) = pn<sup>2</sup> + qn + r ≤ pn<sup>2</sup> + qn<sup>2</sup> + rn<sup>2</sup> = (p + q + r)n<sup>2</sup> for all n ≥ 1. This inequality is exactly what the definition of O(⋅) requires: T(n) ≤ cn<sup>2</sup>, where c = p + q + r.\\ 
  
-**Asymptotic Lower Bounds**\\+===Asymptotic Lower Bounds===
 We want to show that this upper bound is the best one possible. To do this, we want to express the notion that for arbitrarily large input sizes n, the function T(n) is at least a constant multiple of some specific function f(n). Thus, we say that T(n) is Ω(f(n)) if there exist constants ε > 0 and n<sub>0</sub> ≥ 0 so that for all n ≥ n<sub>0</sub>, we have T(n) ≥ ε⋅f(n). We want to show that this upper bound is the best one possible. To do this, we want to express the notion that for arbitrarily large input sizes n, the function T(n) is at least a constant multiple of some specific function f(n). Thus, we say that T(n) is Ω(f(n)) if there exist constants ε > 0 and n<sub>0</sub> ≥ 0 so that for all n ≥ n<sub>0</sub>, we have T(n) ≥ ε⋅f(n).
  
-**Asymptotically Tight Bounds**\\+===Asymptotically Tight Bounds===
 If a function T(n) is both O(f(n)) and Ω(f(n)), we say that T(n) is Θ(f(n)). In this case, we say that f(n) is an asymptotically tight bound for T(n). For example, the analysis above shows that T(n) = pn<sup>2</sup> + qn + r is Θ(n<sup>2</sup>).\\  If a function T(n) is both O(f(n)) and Ω(f(n)), we say that T(n) is Θ(f(n)). In this case, we say that f(n) is an asymptotically tight bound for T(n). For example, the analysis above shows that T(n) = pn<sup>2</sup> + qn + r is Θ(n<sup>2</sup>).\\ 
 \\  \\ 
-**Properties of Asymptotic Growth Rates**\\ +===Properties of Asymptotic Growth Rates=== 
 **//Transitivity//**\\  **//Transitivity//**\\ 
 If a function f is asymptotically upper-bounded by a function g, and if g in turn is asymptotically upper-bounded by a function h, then f is asymptotically upper-bounded by h.\\  If a function f is asymptotically upper-bounded by a function g, and if g in turn is asymptotically upper-bounded by a function h, then f is asymptotically upper-bounded by h.\\ 
Line 37: Line 37:
 Suppose that f and g are two functions (taking non-negative values) such that g = O(f). Then f + g = Θ(f). In other words, f is an asymptotically tight bound for the combined function f + g.\\  Suppose that f and g are two functions (taking non-negative values) such that g = O(f). Then f + g = Θ(f). In other words, f is an asymptotically tight bound for the combined function f + g.\\ 
 \\  \\ 
-**Asymptotic Bounds for Some Common Functions**\\ +===Asymptotic Bounds for Some Common Functions=== 
 **//Polynomials//**\\  **//Polynomials//**\\ 
 Let f be a polynomial of degree d, in which the coefficient a<sub>d</sub> is positive. Then f = O(n<sup>d</sup>).\\  Let f be a polynomial of degree d, in which the coefficient a<sub>d</sub> is positive. Then f = O(n<sup>d</sup>).\\ 
courses/cs211/winter2018/journals/boyese/chapter2.1517862664.txt.gz · Last modified: by boyese
Show pageOld revisions
Media ManagerBack to top
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0