i do not understand asymptotic notation

1 files changed, 63 insertions, 0 deletions

diff --git a/notes.md b/notes.md
index 38a2d88..45666ac 100644
--- a/notes.md
+++ b/notes.md
@@ -826,3 +826,66 @@ BINARY-SEARCH(A, t, s, e)
   else
     return BINARY-SEARCH(A, t, mid+1, e)
 ```
+
+# Growth of Functions
+
+When we look at input sizes large enough to make only the order of growth of the
+running time relevant, we are studying the _asymptotic_ efficiency of
+algorithms.
+
+
+## Asymptotic Notation
+
+Natural numbers. `N = {0,1,2,...}`. This notation is useful for describing the
+worst case running time of function `T(n)`.
+
+### 𝚯-notation
+
+The worst case running time of insertion sort is `T(n) = 𝚯(n^2)`.
+
+
+`f(n) = O(g(n))` means that there are some suitable constants `c > 0` and `n0 >0`
+such that f is bounded by c of g of n for all of n.
+
+Ex.
+
+`2*n^2 = O(n^3)`
+
+big o is like less than or equal to.
+set definitiion
+
+
+`2n^2` is in the set of `O(n^3)`
+
+Macro Convention:
+  A set in a formula represents an anonymous function in that set.
+
+Ex. `f(n) = n^3 + O(n^2)`.
+  This means that there is a function h(n) that is in big o of n squared such that
+  `f(n) = n^3 th(n)`. WHAT... THE WHAT?
+
+Ex. `n^2 + O(n) = O(n^2)`. equals means `is`. is means everything over here means something over here.
+Everything on the left exists on the right side, but the right is not the same as
+the left side.
+
+Big omega notation. _()_
+  _()_(g(n)) = {f(n) there exists consts c > 0
+
+
+* running time: `𝚯(n)`. Theta of n.
+  * When we say that a particular running time is theta of n, we're saying that
+    once `n` gets large enough, the running time is at least `k1*n` and at most
+    `k2*n` for some constants `k1` and `k2`.
+  * we don't have to worry about which time units we're using.
+  * when we use big-𝚯 notation, we're saying that we have an *asymptotically
+    tight bound* on the running time.
+  * `𝚯(1)`: Constant time.
+  * `𝚯(log n)`:
+  * `𝚯(n)`:
+  * `𝚯(nlog n)`:
+  * `𝚯(n^2)`:
+  * `𝚯(n^2 * log n)`:
+  * `𝚯(n^3)`:
+  * `𝚯(2^n)`:
+  * `𝚯(n!)`:
+* rate of growth