N Log N

• function: $\Theta(n \log n)$.
• recurrence: T(1) = 1, T(n) = n + 2 T(n/2)
• context: Scan, divide, recurse on both halves.
• examples: Sorting, Fast Fourier Transform.
• variations: $T(n) = \log n + T(n-1)$.