Recurrence Relations

Equations describing a recursive algorithm's cost.

Intermediate

Merge sort: $T(n) = 2T(n/2) + O(n)$ . Binary search: $T(n) = T(n/2) + O(1)$ . Solve by substitution, recursion trees or the Master theorem.

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)