Introduction to algorithm未知笔记

Chapter 2
P41
Horner's rule(for evaluating a polynomial) is worth recording.

Chapter 3
P47
证明 f(n) = an^2 + bn + c = θ(n^2)
where a, b, and c are constants and a > 0.
设 c1 n^2 <= an^2 + bn + c <= c2 n^2
令 c1 = a/4, c2 = 7a/4,
a/4 n^2 <= an^2 + bn + c <= 7a/4 n^2
令 n0 = 2 max(|b|/a, sqrt(|c|/a))
当 n > n0 时， c1 n^2 <= an^2 + bn + c <= c2 n^2 成立


P54
证明 ceil( ceil(x/a)/b ) = ceil( x / ab )

P58
iterated logarithm 重对数
在研究生概率大数定理教学计划里看到，但我的书里面没有。