Midterm cheat sheet CS381

For every b > 1 and every x > 0, we have logb n = O(n^x).
For every r > 1 and every d > 0, we have n^d = O(rⁿ).

2^log₃n = n^log₂3

T(n) = T(n/3) + T(2n/3) + cn, T(n) is O(nlgn).

Proof of T(n) is Ω(nlgn):

     T(n) ≥ (work done by leftmost leaves) + (cn⋅h_left)
             ≥T1⋅2log₃(n)+cn⋅log₃(n)
             =T1⋅nlog₃(2)+cn⋅log₃(n)
             ≈T1⋅n^0.63+cn⋅log₃(n)
             =Ω(nlgn)