视频地址：

http://open.163.com/movie/2010/12/2/E/M6UTT5U0I_M6V2T4T2E.html

f(n) = O(g(n)) means

0 <= f(n) <= cg(n)

Macro convention 宏

O(n) upper bound

Ω(n) lower bound

Θ(n) between O(n) and Ω(n)

 

Solving recurrences

1, Guess the form

2, Verify by induction

3, solve the constants

 

Ex: T(n) = 4T(n/2) + n

T(1) = Θ(1)

Guess: T(n) = O(n^3)

Assume T(k) ≦ ck^3 for k < n

T(n) = 4T(n/2) + n ≦ 4c(n/2)^3 + n = 1/2 c n^3 + n = cn^3 - (1/2 cn^3 - n) ≦ cn^3;

if (1/2 cn^3 - n) > 0 and c > 1