Exponential

• function: $\Theta(2^n)$.
• recurrence: T(1) = 1, T(n) = 2 T(n-1)
• context: Solve both of two slightly smaller versions of problem.
• examples: Number of nodes in a binary tree.
• variations: T(n) = 1 + 2 T(n-1), other exponentials: T(n) = k T(n-1).