Opening your learning space
Starting the app …
Opening your learning space
Starting the app …
A recurrence models a recursive algorithm through the number and size of its subproblems plus non-recursive work per call.
Free to browse · flashcards or a multiple-choice quiz · import from Essential
Formula
n problem size; a number of subproblems; b reduction factor; T and f in operation counts
| Symbol | Meaning | Unit |
|---|---|---|
| Total cost for input size n | operations | |
| Number of recursive subproblems | dimensionless | |
| Factor by which each subproblem shrinks | dimensionless, b>1 | |
| Non-recursive work at one call | operations |
T(n)=aT(n/b)+f(n), \quad T(1)=\Theta(1)T(n)=aT(n/b)+f(n) models regular divide-and-conquer algorithms with a equal-sized recursive calls. A base case and a rounding convention for n are required. The Master theorem compares f(n) with n^(log_b a), but applies only when its conditions hold. A recurrence counts a chosen computational cost, not seconds; unequal partitions or irregular recursive structure may need another method.
T(n)=aT(n/b)+f(n) models regular divide-and-conquer algorithms with a equal-sized recursive calls. A base case and a rounding convention for n are required. The Master theorem compares f(n) with n^(log_b a), but applies only when its conditions hold. A recurrence counts a chosen computational cost, not seconds; unequal partitions or irregular recursive structure may need another method.
A recurrence models a recursive algorithm through the number and size of its subproblems plus non-recursive work per call.
Defining relation
The equation states the defining relation within its stated domain.
Use the example for Divide-and-conquer runtime recurrence to explain which inputs determine the requested output.
The example connects concrete inputs to its result.
A recurrence models a recursive algorithm through the number and size of its subproblems plus non-recursive work per call.
The relation applies only under its stated assumptions.
Applying the relation to a different case without checking its stated assumptions.
Check the validity range before substituting values: T(n)=aT(n/b)+f(n) models regular divide-and-conquer algorithms with a equal-sized recursive calls. A base case and a rounding convention for n are required. The Master theorem compares f(n) with n^(log_b a), but.
Formula cluster
A recurrence models a recursive algorithm through the number and size of its subproblems plus non-recursive work per call.
MergeSort satisfies T(n)=2T(n/2)+cn with constant-size base cases. Each level costs Θ(n), and there are Θ(log n) levels, so T(n)=Θ(n log n).
Analyze recursive algorithms, make recursion levels explicit and compare divide-and-conquer strategies.
Here is how to work through a typical Divide-and-conquer runtime recurrence (T(n) = aT(n/b) + f(n)) task step by step:
Task
Use the example for Divide-and-conquer runtime recurrence to explain which inputs determine the requested output.
Solution path
The example connects concrete inputs to its result.
A recurrence models a recursive algorithm through the number and size of its subproblems plus non-recursive work per call.
The relation applies only under its stated assumptions.
The relation T(n)=aT(n/b)+f(n), \quad T(1)=\Theta(1) summarizes A recurrence models a recursive algorithm through the number and size of its subproblems plus non-recursive work per call. Read it as a model for defined quantities, not as an automatic claim about every real situation. In the example MergeSort satisfies T(n)=2T(n/2)+cn with constant-size base cases. Each level costs Θ(n), and there are Θ(log n) levels, so T(n)=Θ(n log n)., symbols are connected to concrete values and the result is interpreted in context. Validity limit: T(n)=aT(n/b)+f(n) models regular divide-and-conquer algorithms with a equal-sized recursive calls. A base case and a rounding convention for n are required. The Master theorem compares f(n) with n^(log_b a), but Source: MIT OpenCourseWare, 6.006 Introduction to Algorithms, Recitation 3: “Recurrences”.
First write down the requested quantity and all given values with their symbols. Substitute them into the defining relation and check unit consistency. The example MergeSort satisfies T(n)=2T(n/2)+cn with constant-size base cases. Each level costs Θ(n), and there are Θ(log n) levels, so T(n)=Θ(n log n). provides a worked check: formula and result must have compatible scale and meaning; round only at the end. Validity limit: T(n)=aT(n/b)+f(n) models regular divide-and-conquer algorithms with a equal-sized recursive calls. A base case and a rounding convention for n are required. The Master theorem compares f(n) with n^(log_b a), but Source: MIT OpenCourseWare, 6.006 Introduction to Algorithms, Recitation 3: “Recurrences”.
The formula applies only when quantities are defined as in the source and background. Check boundary cases, measurement conditions and whether an approximation rather than equality is intended. Substitution can be algebraically correct yet technically wrong when assumptions fail or the population or system boundary changes. Validity limit: T(n)=aT(n/b)+f(n) models regular divide-and-conquer algorithms with a equal-sized recursive calls. A base case and a rounding convention for n are required. The Master theorem compares f(n) with n^(log_b a), but Source: MIT OpenCourseWare, 6.006 Introduction to Algorithms, Recitation 3: “Recurrences”.
The stated units are: n problem size; a number of subproblems; b reduction factor; T and f in operation counts. Convert values to a consistent unit system before substitution; counts, percentages and dimensionless ratios are not interchangeable. The variable list states the role of each symbol. Dimensional analysis catches many errors but does not replace checking the formula's assumptions. Validity limit: T(n)=aT(n/b)+f(n) models regular divide-and-conquer algorithms with a equal-sized recursive calls. A base case and a rounding convention for n are required. The Master theorem compares f(n) with n^(log_b a), but Source: MIT OpenCourseWare, 6.006 Introduction to Algorithms, Recitation 3: “Recurrences”.
Comparison helps when both quantities address the same question but emphasize different properties. Report the definition, input data, threshold or averaging with the value. The source MIT OpenCourseWare, 6.006 Introduction to Algorithms, Recitation 3: “Recurrences”. supports the definition used here; other conventions can differ. Choose the measure to match the learning or analysis goal. Validity limit: T(n)=aT(n/b)+f(n) models regular divide-and-conquer algorithms with a equal-sized recursive calls. A base case and a rounding convention for n are required. The Master theorem compares f(n) with n^(log_b a), but Source: MIT OpenCourseWare, 6.006 Introduction to Algorithms, Recitation 3: “Recurrences”.
Quanta exam set
Curated exam set for "Divide-and-conquer runtime recurrence":
Question (front)
Which formula describes Divide-and-conquer runtime recurrence?
Answer in your set
Question (front)
How do you rearrange Divide-and-conquer runtime recurrence for Defining relation?
Answer in your set
Question (front)
Which common mistake happens with Divide-and-conquer runtime recurrence?
Answer in your set
+ 7 more cards: units, variables, derivation, example, exam task
The formula set contains 10 cards. After importing, review them and start practicing; your ratings determine later review intervals.
This list names subject references and further reading. A page or section number appears when it is part of the reference; these are not verbatim quotations.
Create a curated FSRS exam set for T(n) = aT(n/b) + f(n): formula recall, variables, derivation, rearrangement, worked example, common mistakes and exam context.
Curated formula set · LaTeX · FSRS spaced repetition · import from Essential