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

instrument mechanism / verified-clean

# Time Complexity of Recursive Algorithm (Master Theorem Solver) mechanism

The inspectable method record for Time Complexity of Recursive Algorithm (Master Theorem Solver), kept separate from implementation and qualification.

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

## Model scope

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.

- 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.

## Units and conventions

- 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.

## Inspectable vector

One of 4 source-bound review vectors:

````
{
  "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)."
}
````

## Failure boundary

**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.

## Other records

[01**Overview**](<https://guthlabs.ai/docs/instruments/time-complexity-of-recursive-algorithm-master-theorem-solver/>)[03**Implementation**](<https://guthlabs.ai/docs/instruments/time-complexity-of-recursive-algorithm-master-theorem-solver/implementation/>)[04**Qualification**](<https://guthlabs.ai/docs/instruments/time-complexity-of-recursive-algorithm-master-theorem-solver/qualification/>)

## Sources and evidence

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

- `VERIFIED_LEDGER.json`

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

- `BOUNDARY_HAZARD_CATALOG.json`