Time Complexity of Recursive Algorithm (Master Theorem Solver) implementation

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

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