Master Theorem

T(n) = a * T(n / b) + f(n)
x    = log_b(a)
T(n) = θ(n^x)          if f(n) = O(n^(x-ε))
       θ(n^x * lg(n))  if f(n) = θ(n^x)
       θ(f(n))         if f(n) = Ω(n^(x+ε)) 
                          and a * f(n/b) <= c * f(n)

Greedy

• At each step, make the "best" next choice.
• Never backtrack or change past choices.
• Never look ahead to see if this choice has negative consequences.

Read more...