Source: https://guthlabs.ai/docs/instruments/time-complexity-of-recursive-algorithm-master-theorem-solver/

instrument / verified-clean

# Time Complexity of Recursive Algorithm (Master Theorem Solver)

The current ledger marks this instrument verified clean within the source-bound verification corpus.

Status: **VERIFIED_CLEAN**Lifecycle: **verified-clean**

## Inspectable records

[01**Overview**Purpose and lifecycle](<https://guthlabs.ai/docs/instruments/time-complexity-of-recursive-algorithm-master-theorem-solver/>)[02**Mechanism**Method and assumptions](<https://guthlabs.ai/docs/instruments/time-complexity-of-recursive-algorithm-master-theorem-solver/mechanism/>)[03**Implementation**Binding and validation](<https://guthlabs.ai/docs/instruments/time-complexity-of-recursive-algorithm-master-theorem-solver/implementation/>)[04**Qualification**Evidence and errata](<https://guthlabs.ai/docs/instruments/time-complexity-of-recursive-algorithm-master-theorem-solver/qualification/>)

## Ledger state

The current ledger marks this instrument verified clean within the source-bound verification corpus.

**Area**: Computing & Information

**Tranche**: tranche-6

**Evidence ID**: t6-104

**Ledger rows**: 1

No ledger note is attached.

## Review findings

The core method is the standard three-case Master Theorem, but the specification does not state the exact case conditions, regularity requirement, input constraints, or supported grammar for f(n). The honest-label limitation is directionally correct but should explicitly include these restrictions. No iterative convergence requirement applies because this instrument is a symbolic/asymptotic classifier, not an iterative solver.

### Formula and scope findings

- The formula description is incomplete: the three standard cases require explicit conditions. With p=log_b(a), Case 1 requires f(n)=O(n^(p-epsilon)) for some epsilon>0; Case 2 requires f(n)=Theta(n^p log^k n) for k>=0; Case 3 requires f(n)=Omega(n^(p+epsilon)) plus the regularity condition a f(n/b)<=c f(n) for some constant c<1.

- Comparing only the polynomial degree of f(n) is insufficient to distinguish Case 2 logarithmic factors or functions such as n^p log n, n^p/log n, and non-polynomial terms.

- The solver needs explicit validity constraints a>=1, b>1, and a,b as constants independent of n. It should also state assumptions about nonnegative asymptotic f(n) and a base-case cost.

- The claimed scope should explicitly reject or flag recurrences outside the standard form, including unequal subproblem sizes, additive terms not expressible as f(n), floors and ceilings requiring special handling, and non-polynomial or irregular f(n) for which the standard theorem conditions cannot be established.

### Unit assumptions

- n is a positive dimensionless input-size variable; logarithm base does not affect Theta classification, so log means any fixed base greater than 1.

- a is the number of recursive subproblems and b is the shrink factor, with a>=1 and b>1; both are assumed constant with respect to n.

- f(n) is the asymptotic nonrecursive work per call and is assumed sufficiently well-behaved and nonnegative for the selected Master Theorem case.

- The recurrence has a valid constant-size base case; the displayed Theta bounds suppress constant base-case and per-call-cost factors.

## Boundary hardening

**BREAK_CLAIMED** · SELF_FLAGGED

The solver specification has an explicit undefined-input hazard at b=1: log_b(a) divides by log(1)=0 and the recurrence does not shrink. Negative f(n) also exposes an unstated sign convention that may cause inconsistent acceptance or classification.

## Errata and corrections

No applied erratum is attached to this unique-name record.

## Inspectable example

4 review vectors are recorded. One source-bound sample is shown below.

````
{
  "inputs": {
    "a": 2,
    "b": 2,
    "f(n)": "n",
    "base_case": "T(1)=1"
  },
  "expected_outputs": {
    "p": "log_2(2)=1",
    "case": "Case 2",
    "theta_bound": "Theta(n log n)",
    "explanation": "f(n)=Theta(n^p), so this is Case 2 with k=0"
  },
  "working": "1. Compute p=log_b(a)=log_2(2)=1. 2. Compute n^p=n^1=n. 3. Compare f(n)=n with n^p=n: f(n)=Theta(n^p). 4. Case 2 gives T(n)=Theta(n^p log^(0+1)n)=Theta(n log n)."
}
````

## Related workflows

No source-defined multi-instrument workflow membership is recorded.

## Sources and evidence

These pointers bind the page to evidence. They do not grant authority or collapse verification into deployment.

- `VERIFIED_LEDGER.json · VERIFIED_CLEAN`

- `evidence-tranche6/tranche6-results.json`

- `BOUNDARY_HAZARD_CATALOG.json`