add notes on bigO, omega and theta notation.

1 files changed, 76 insertions, 2 deletions

diff --git a/notes.md b/notes.md
index 45666ac..e51a80f 100644
--- a/notes.md
+++ b/notes.md
@@ -877,8 +877,7 @@ Big omega notation. _()_
     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.
+  * 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)`:
@@ -889,3 +888,78 @@ Big omega notation. _()_
   * `𝚯(2^n)`:
   * `𝚯(n!)`:
 * rate of growth
+
+
+Abdul Bari https://www.youtube.com/watch?v=A03oI0znAoc
+Asymptotic Notations Big Oh - Omega - Theta
+
+Representing a simple form of a function
+
+We need a simple method for representing time complexity.
+
+| symbol | english | use |
+| -------- | --- | --- |
+| O | big-oh | upper bound of a function |
+| 𝚯 | theta notation | average bound of a function |
+| _()_ | big-omega | lower bound of a function |
+
+Theta is useful.
+
+1 < logn < sqrt(n) < n < nlogn < n^2 < n^3 ... < 2^n < 3^n ... < n^n
+
+Big-oh
+------
+
+The function `f(n)=O(g(n))` if there exist poitive constants c and n0
+such that `f(n) <= c * g(n) V n >= n0`
+
+Example:
+
+```
+  f(n) = 2n+3
+  2n+3 <= __ 10n __ n>=1
+  f(n)        c*g(n)
+  f(n) = O(n)
+
+  2n+3 <= 2n+3n will always work.
+```
+
+instead of guessing the value you can make it as 2n+3
+
+
+Omega
+----
+
+The function `f(n) = omega(g(n)) if positive contstants c and n0`
+such that `f(n) >= c * g(n) V n>=n0`
+
+e.g.
+
+```
+f(n) = 2n+3
+f(n)    c * g(n)
+
+2n+3 >= log n V n>=1
+f(n)     c * g(n)
+
+
+ true f(n) = omega(n)   (most useful answer)
+ true f(n) = omega(logn)
+```
+
+Theta
+-----
+
+The funciton `f(n)=theta(g(n)) if 3 +ve constants c1,c2 and n0`
+such that `c1*g(n) <= f(n) <= c2*g(n)`
+
+f(n) = theta(n)
+
+```
+eg.
+f(n) = 2n + 3
+1*n   <= 2n + 3 <= 5xn
+c*g(n)   f(n)
+```
+
+