Log

• function: $\Theta(\log n)$.
• recurrence: T(1) = 1, T(n) = 1 + T(n/2)
• context: Recurse on half of input and throw half away.
• examples: Euclid, Repeated Squaring, search in balanced trees.
• variations: T(n) = 1 + T(99 n/100), T(n) = T(2n/3)+n/3.