commit fb978921872b282ccee6c91bd88974a82503fc7a
parent ff57f1026407568cacbe09a61466a478b5a32c03
Author: Andrew <andrewlaack1@gmail.com>
Date: Tue, 3 Sep 2024 09:44:23 -0500
Added some notes about discrete math
Diffstat:
5 files changed, 33 insertions(+), 6 deletions(-)
diff --git a/Algorithms.md b/Algorithms.md
@@ -31,6 +31,7 @@ Ch 2 (Big-O and Asymptotic Complexity):
Ch 3 (state analysis):
- [StateAnalysis](StateAnalysis.md)
+ - StirlingsFormula
#### Intro To Algorithms (MIT)
diff --git a/DiscreteMath.md b/DiscreteMath.md
@@ -103,7 +103,7 @@ Unit 2.4 (integers and division):
- [CaesarCipher](CaesarCipher.md)
- [VigenereCipher](VigenereCipher.md)
- [EuclideanAlgorithm](EuclideanAlgorithm.md)
- - linear combination
- - linear congruence
- - pseudoprime
- -
+ - [LinearCombination](LinearCombination.md)
+ - [LinearCongruence](LinearCongruence.md)
+
+Unit 6.1 (The Basics of Counting)
diff --git a/LinearCombination.md b/LinearCombination.md
@@ -1,4 +1,4 @@
-:lin-alg:
+:lin-alg: :discrete:
# Linear Combination
Khan
diff --git a/LinearCongruence.md b/LinearCongruence.md
@@ -0,0 +1,8 @@
+:discrete:
+# Linear Congruence
+
+Ch 2.4
+
+## Notes
+
+**Definition:** A linear congruence is a congruence of the form ax \equiv b (mod c) where a,b,c are integers and x is a variable.
diff --git a/StateAnalysis.md b/StateAnalysis.md
@@ -5,4 +5,22 @@ Ch 3
## Notes
-**Definition:** State analysis, in the context of algorithms, is a strategy for computing the time complexity of an algorithm that analyzes the state of the algorithm instead of describing each line of code and their associated complexity which becomes unruly as algorithms become more complex.
+**Definition:** State analysis, in the context of algorithms, is a strategy for computing the time complexity of an algorithm that analyzes the current state of the algorithm instead of describing each line of code and their associated complexity which becomes unruly as algorithms become more complex.
+
+### Steps
+
+1. Choose a variable that captures as much state as possible (state variable)
+2. Find an upper bound for the domain of the variable
+3. Find upper bound for number of instructions at each state value
+4. Multiply results from steps 2 and 3 to find total complexity (worst case complexity)
+
+### Example (bubble sort)
+
+1. State variables are i and j
+2. Upper bound for i is n+1 upper bound for j is also n thus n(n+1)
+3. 11 total statements thus 11 is worst case number of statements per iteration (this is based on implementation, assignment, etc.)
+4. At most 11n(n+1) = 11n^2 + 11n time complexity
+
+As can be seen above, this is not entirely accurate to what we would find by evaluating each line of code, but this is generally close enough and only off by some constant factor.
+
+One limit of this is when n=0 we find the above algorithm also performs 0 instructions. This is because we don't take into account the initial overhead of assignments and such as we only care about the bulk of the complexity that comes from the iteration/computation part of the algorithm.
