📗 -> 10/8/24: Master Theorem
🎤 Vocab
❗ Unit and Larger Context
Linear Selection
A cool recurrence that uses the formula T(n) = T(n/7) + T(5k/7) + O(n)
You’ll end up with 2 kinds of equations:
Methods for Solving Recurrence:
So far we have studied:
- Recurrence Tree Method
- Substitution
We will cover next:
3) Master Theorem
✒️ -> Scratch Notes
Substitution:
- Guess
- Rectify via induction using def of Big-O
- Solve for constants, c,
T(n) = T(n/6) + T(2n/6) + O(n)
Guess T(n) = O(n)
n=k, assume it is Big O and find c and
T(k) = T(k/6) + T(2k/6) + O(k)
c(k/6) + c(2k/6) + a(k)
3/6 ck + ak
T(n) = 2T(n/2) + O(n)
Merge sort…, so we know its actually nlogn
Guess T(n) = O(n)
T(n) <= cn for all n <= k-1
T(k) = 2T(k/2) + k <= ck
2c(k/2) + k <= ck
ck + k <= ck
this is an example of where substitution fails
T(n) = 2T(n/2) + n, Guessing that T(n)=O(nlogn)
T(n) = O(nlogn)
<= cnlogn <- Definition of big O
T(k) <= 2T(k/2) + k <= cklogk
2c(k/2)log(k/2) + k
ck[logk - log2 2] +k <= cklogk
cklogk -ck + k <= cklogk
-ck + k <= 0
1 <= c
Step Guidelines:
- Inductive Hypothesis, assume T(n) <= ck for all n <= k-1
- Solv efor c,
when n=k
🧪-> Example
- List examples of where entry contents can fit in a larger context
🔗 -> Related Word
- Link all related words