From 5c664a3d22d5062afa95f07ac294d425247877de Mon Sep 17 00:00:00 2001
From: mo khan <mo@mokhan.ca>
Date: Sun, 7 Nov 2021 12:31:43 -0700
Subject: write out the assignment questions

---
 notes.md | 48 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 48 insertions(+)

(limited to 'notes.md')

diff --git a/notes.md b/notes.md
index 74b0fbb..c1b4206 100644
--- a/notes.md
+++ b/notes.md
@@ -1395,3 +1395,51 @@ n^n
   3125000000000003092243963814697472323387062050608712810316261079389878210275894062864994740260526805850873354374897838591668659178014794724456808448969682640589359820361298594587056678177036967084032 ┤                                                                      │
                                                                                                                                                                                                         0 ┼──────────────────────────────────────────────────────────────────────╯
 ```
+
+
+
+https://www.udemy.com/course/datastructurescncpp/learn/lecture/13319452#overview
+
+Asymptotic Notation Video
+
+
+| 1 < lg n < n < n lg n < n^2 < n^3 < .... < 2^n < 3^n ... < n^n |
+
+                        | polynomial |     |      exponential    |
+
+
+1 : push into stack
+lg n : AVL tree
+n : max item in array
+n log n : quick sort
+n^2 : matrix, graph
+2^n : exponential time complexities
+
+Don't start n from n = 0 or n = 1.
+Starting value of n can be any starting value
+
+n 0 --|---- infinity
+      |------------
+
+
+
+| n^3 |       2^n |
+| ---     | ---- |
+| 2^3=8     | 2^2=4 |
+| 10^3=1000 | 2^10=1024 |
+| 11^3=1221 | 2^11=2048 |
+
+
+
+f(n) = n   ---> O(n)
+f(n) = n^2 ---> O(n^2)
+
+f(n) =  n
+       sigma i   ----- 1 + 2 + 3 + .... + n  = ((n(n+1))/2) = O(n^2)
+        i=1
+
+| lower bound | omega |
+| upper bound | big-oh |
+| tight bound | theta |
+
+Useful when you cannot get the exact polynomial for a function.
-- 
cgit v1.2.3