ECS122A-L5

📗 -> 10/10: Algorithm Analysis Continued

---

🎤 Vocab

❗ Unit and Larger Context

Master Theorem

T(n) = AT(n/B) + n

✒️ -> Scratch Notes

Worked Example:

Tree Method:

• n
  • 4(n/2) <- splits off 4 times, does n/2 work
    • 4^2(n/4)
      Work: i is the level,
      Depth:

Steps:

1. Assume T(n) = O(n^2) for all n <= k - 1
   <= cn
2. Solve for c when n=k
   n=k, T(k) = 4T(k/2) + k <= ck^2
   4c(k/2)^2 + k
   ck^2 + k <= ck^2
   k <= 0
   ^ FALSE, not true
   Equation can never be solved. Our O(n) guess was too low
   Again…
   Steps:
3. Assume T(n) = O(n^2) for all n <= k - 1
   <= cn^2 + dn
4. Solve for c when n=k
   n=k, T(k) = 4T(k/2) + k <= ck^2 + dn
   4(c(k/2)^2 + d(k/2))+ k <= ck^2 + dn
   4ck^2 / 4 + 4dk/2 + k <= ck^2 + dn
   2dk +k <= dk
   1dk <= -k
   d <= -1
   ^ FALSE, not true
   Equation can never be solved. Our O(n) guess was too low

Master Theorem

T(n) = At(n/b) + f(n)
vs f(n)
if x is bigger => Case A

Case A: Prove

, then
T(n) = n = O(n^{2-\epsilon})lim \frac{n}{n^{2-\epsilon}} = lim \frac{1}{n^{1-\epsilon}} = 0\epsilon =.5$

Case B: Prove

f(n) = =>
T(n = 2T(n/2) + n <- Mergesort
A=2, B=2, f(n)=n

n=(n) trivial => T(n) = O(nlogn)

T(n) = 9T(n/3) + 5n^2

Trivial,

Case 3: Prove

if
Prove:

2. for some c<1. Find c

T(n) = 4T(n/2) + n^3

🧪-> Example

• List examples of where entry contents can fit in a larger context

🔗 -> Related Word

• Link all related words