Master Theorem
Loosening the restrictions on f(n)
Case 1: f(n)ÎO(nE-e), (e>0), then:
T(n)QÎ(nE)
Case 2: f(n)QÎ(nE), as all node depth contribute about equally:
T(n)QÎ(f(n)log(n))
case 3: f(n)WÎ(nE+e), (e>0), and f(n)ÎO(nE+d), (e³d), then:
T(n)QÎ(f(n)) |
楼主
