Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:bowmang:chapter2 [2018/01/30 03:09] – bowmang | courses:cs211:winter2018:journals:bowmang:chapter2 [2018/01/30 03:10] (current) – bowmang | ||
|---|---|---|---|
| Line 31: | Line 31: | ||
| ===== Chapter 2.2 (Asymptotic Order of Growth) ===== | ===== Chapter 2.2 (Asymptotic Order of Growth) ===== | ||
| - | Runtime Bounds | + | __Runtime Bounds__ |
| * No need to get extremely specific in them as that is an exhaustive effort and unnecessary (unless you are under oppressively fine constraints for an algorithm' | * No need to get extremely specific in them as that is an exhaustive effort and unnecessary (unless you are under oppressively fine constraints for an algorithm' | ||
| * By using a certain level of vagueness, similarities between algorithms start to appear. | * By using a certain level of vagueness, similarities between algorithms start to appear. | ||
| - | Asymptotic | + | __Asymptotic |
| * An upper bound exists if the worst-case running time is less than a constant multiple of f(n). | * An upper bound exists if the worst-case running time is less than a constant multiple of f(n). | ||
| - | Asymptotic | + | __Asymptotic |
| * A lower bound exists if the best-case running time is more than a constant multiple of f(n) for a sufficiently large size N. (necessary to prove scaleability, | * A lower bound exists if the best-case running time is more than a constant multiple of f(n) for a sufficiently large size N. (necessary to prove scaleability, | ||
| - | Asymptotic | + | __Asymptotic |
| * If we can show both an asymptotic upper and lower bound are the same as the run time then we can say we have found the right bounds. | * If we can show both an asymptotic upper and lower bound are the same as the run time then we can say we have found the right bounds. | ||
| * These tight bounds are good to find for worst-case runtime scenarios as they show the runtime precisely. | * These tight bounds are good to find for worst-case runtime scenarios as they show the runtime precisely. | ||
| - | Properties | + | __Properties |
| * Transitivity: | * Transitivity: | ||
| * Sums of Functions: if an upper bound applies to both function F and function G individually then it applies to the sum of the functions F and G. | * Sums of Functions: if an upper bound applies to both function F and function G individually then it applies to the sum of the functions F and G. | ||
| - | Asymptotic | + | __Asymptotic |
| * Polynomials | * Polynomials | ||
| * If a polynomial is to degree D then the runtime is O(n^D). | * If a polynomial is to degree D then the runtime is O(n^D). | ||
