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

instrument implementation / implementation-contract

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

A source-bound implementation contract for Time Complexity of Recursive Algorithm (Master Theorem Solver); deployment and executable qualification remain separate.

Status: **VERIFIED_CLEAN**Lifecycle: **implementation-contract**

## Binding contract

This record describes what an executable surface must bind and validate. It does not claim that a public calculator, package, or production route is deployed.

**Record owner**: Guth Instruments

**Lifecycle**: verified-clean

**Evidence ID**: t6-104

**Effect**: Computation or source lookup only

## Input and validation requirements

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.

## Required corrections

No binding erratum is attached to this unique-name record. Implementers must still preserve the declared units, domain, and failure behavior.

## Inspectable interface fixture

The sample below is evidence for interface and validation tests, not a production implementation.

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

## Other records

[01**Overview**](<https://guthlabs.ai/docs/instruments/time-complexity-of-recursive-algorithm-master-theorem-solver/>)[02**Mechanism**](<https://guthlabs.ai/docs/instruments/time-complexity-of-recursive-algorithm-master-theorem-solver/mechanism/>)[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`