Differences

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

--- courses:cs211:winter2018:journals:holmesr:section_2.2 [2018/01/17 03:52] – holmesr
+++ courses:cs211:winter2018:journals:holmesr:section_2.2 [2018/01/21 00:58] (current) – holmesr
@@ Line 7: / Line 7: @@
 Additionally, we can use both of these components to arrive at an asymptotically tight bound. When T(n) = O(f(n)) = <OMEGA>(f(n)), it is safe to say that T(n) = <THETA>(f(n)). Another way to compute asymptotically tight bounds is to take the limit of f(n)/g(n) as n goes to infinity.
-Finally, asymptotic growth rates have properties of transitivity (if f is bounded by g and g is bounded by h, f is bounded by h so long as f and g are both bounded in the same direction) and the ability to be summed (if f is upper bounded by h and g is upper bounded by h, f+g is upper bounded by h).
+It is also important to note that asymptotic growth rates have properties of transitivity (if f is bounded by g and g is bounded by h, f is bounded by h so long as f and g are both bounded in the same direction) and the ability to be summed (if f is upper bounded by h and g is upper bounded by h, f+g is upper bounded by h).
+Finally, the section includes a brief treatment of asymptotic bounds for common functions. Summarily, it states that for some constants d > 0 r > 0 and n >= 1, O(log n) < O(n<sup>d</sup>) < O(r<sup>n</sup>).