---
title: "Recurrence Relations and the Master Theorem"
description: "A recursive algorithm's cost is written as an equation that refers to itself, such as T(n) = 2T(n/2) + n. Solving it by expansion, by a recursion tree, or by the master theorem gives the running time "
canonical: https://lightmysky.com/learn/computing/recurrence-relations-and-the-master-theorem-mt_aOvLPV7rR8
source: https://lightmysky.com/learn/computing/recurrence-relations-and-the-master-theorem-mt_aOvLPV7rR8.md
retrieved: 2026-09-12
---

> **Agent view.** This is the Markdown twin of the page, for tools and assistants.
> When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md
> API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md
> Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt
> Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json
> Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`.

# Recurrence Relations and the Master Theorem

A recursive algorithm's cost is written as an equation that refers to itself, such as T(n) = 2T(n/2) + n. Solving it by expansion, by a recursion tree, or by the master theorem gives the running time without tracing a single call.

Subject: Computing · Area: Algorithms & Data Structures · Ages 18 to 20
Page: https://lightmysky.com/learn/computing/recurrence-relations-and-the-master-theorem-mt_aOvLPV7rR8

## Ready when they can

- Write the recurrence for merge sort and for binary search from the code
- Expand a recurrence into a tree and sum the work level by level
- Apply the master theorem and say which of its cases a given recurrence falls in

## Lesson: Solving the cost of recursion

Some methods call themselves on smaller inputs. You write their total cost as an equation that mentions itself. For example, T(n) = 2T(n/2) + n says the cost on size n is twice the cost on half the input, plus linear work outside the calls.

**Example.** Merge sort splits the list in half, sorts both halves, then merges in linear time, so its recurrence is T(n) = 2T(n/2) + n. Binary search checks the middle once and keeps only one half, so its recurrence is T(n) = T(n/2) + 1.

To solve a recurrence, expand it into a tree. Each level of the tree is one round of calls. You add up the work level by level until the pieces reach size one.

**Tip.** The master theorem sorts these recurrences into three cases. In the first case the leaves dominate, in the second every level ties, and in the third the work outside the calls dominates. Name the case by comparing the leaf work with the outside work.

**Recap.** Write the cost as an equation about itself, expand it level by level, then name the master theorem case.

## Practice

16 questions on this page, each with its working shown.

## Needs first

- [Proof by Induction and Strong Induction](https://lightmysky.com/learn/mathematics/proof-by-induction-and-strong-induction-mt_7lvC02JBOC)
- [Asymptotic Notation Made Precise](https://lightmysky.com/learn/computing/asymptotic-notation-made-precise-mt_B0Z6Syy8Ve)
- [Geometric Series and the Sum to Infinity](https://lightmysky.com/learn/mathematics/geometric-series-and-the-sum-to-infinity-mt_HHxFOv6vXS)
- [Merge Sort and Divide and Conquer](https://lightmysky.com/learn/computing/merge-sort-and-divide-and-conquer-mt_OAutL4c7_l)
- [Recursion and the Call Stack](https://lightmysky.com/learn/computing/recursion-and-the-call-stack-mt_VGjfeF3F2e)

## Opens up

- [Dynamic Programming: Optimal Substructure and Overlapping Subproblems](https://lightmysky.com/learn/computing/dynamic-programming-optimal-substructure-and-overlapping-subproblems-mt__hWkCDnzNY)
- [Divide and Conquer as a Design Method](https://lightmysky.com/learn/computing/divide-and-conquer-as-a-design-method-mt_YITRNb-HTE)