Review 001

Complexity Analysis

Tree Method:

• number of levels

• number of node per level

• work per level

levels: nodes/level: work/node: work/level = nodes / level * work / node

sum_0^{log(n)} n/2^i C0 = O(n) sum_0^{log(n)} 3^i C0 = O(n) log(n/2^i) = log(n) - log(2^i) = log(n)