Computer Science
Advanced

Master Theorem (form)

Analyzes running time of divide-and-conquer algorithms.

Formula

T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)

Variables

aSubproblems
bDivision factor
f(n)Work per level

Example

Merge sort solves T(n) = 2T(n/2) + n, which the Master Theorem gives as O(n log n).

Did You Know?

The Master Theorem instantly gives the runtime of divide-and-conquer algorithms like merge sort.

complexityalgorithmsrecurrence