analysis

Analysis

"Recurrence Relation"
T(n) = 2*T(n/2) + n  ==>  O(nlogn)

- 2 recursive calls on size n/2, logic that determines case
- big O is kind of sloppy normally

T(0) = 1 usually (one way we are sloppy)
we also treat the +n part with normal big O rules (simplified coefficients etc)

===

Cheater's Theorem
Master Theorem

T(n) = a*T(n/b) + n^d

if a < b^d then O(n^d)
if a = b^d then O(n^d logn)
if a > b^d then O(n^{log_b a})

T = 2*T(n/2) + n
a = 2, b = 2, d = 1