Computer Science
Advanced

Master Theorem Form

General form for analyzing divide-and-conquer recurrences.

Formula

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

Variables

aSubproblems
bDivision factor
f(n)Extra work

Example

Solves many recursive runtimes

Did You Know?

The Master Theorem instantly reveals the runtime of most divide-and-conquer algorithms.

algorithms