Time Complexity Comparator for Sorting Algorithms 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-072

Effect

Computation or source lookup only

Input and validation requirements

Invalid boundary inputs can reach numeric plotting: merge sort at n=0 evaluates n log2(n), which is undefined, and negative n is ambiguous or invalid as a collection size. The instrument needs explicit validation for n=0 and negative or otherwise malformed ranges, plus a documented bubble-sort implementation convention for branch-dependent counts.

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": {
    "algorithms": [
      "bubble",
      "insertion",
      "merge"
    ],
    "n_range": [
      1,
      8
    ],
    "bubble_variant": "early_exit",
    "merge_implementation": "array_with_auxiliary_buffer",
    "plot_model": "representative_class_functions",
    "log_base": 2
  },
  "expected_outputs": {
    "complexity_table": {
      "bubble": {
        "best": "O(n)",
        "average": "O(n^2)",
        "worst": "O(n^2)",
        "auxiliary_space": "O(1)"
      },
      "insertion": {
        "best": "O(n)",
        "average": "O(n^2)",
        "worst": "O(n^2)",
        "auxiliary_space": "O(1)"
      },
      "merge": {
        "best": "O(n log n)",
        "average": "O(n log n)",
        "worst": "O(n log n)",
        "auxiliary_space": "O(n)"
      }
    },
    "sampled_plot_points": {
      "bubble_best": {
        "1": 1,
        "8": 8
      },
      "bubble_average": {
        "1": 1,
        "8": 64
      },
      "insertion_best": {
        "1": 1,
        "8": 8
      },
      "insertion_average": {
        "1": 1,
        "8": 64
      },
      "merge_all": {
        "1": 0,
        "8": 24
      }
    },
    "curve_features": {
      "n": "linear through the origin",
      "n_squared": "quadratic through the origin",
      "n_log2_n": "superlinear; value is 0 at n=1 under the representative n log2(n) model"
    }
  },
  "working": "1) Bubble with early exit: already sorted input performs one pass, so best class is O(n); reversed/random inputs require quadratic passes, so average and worst are O(n^2). 2) Insertion sort: one comparison per item in the best case gives O(n); average and reverse-order cases sum 1+2+...+(n-1)=n(n-1)/2, hence O(n^2). 3) Merge sort performs log2(8)=3 merge levels, and each level processes 8 items: 8*3=24, giving the representative value n log2(n)=24. 4) At n=1, n=1, n^2=1, and n log2(n)=1*0=0. These plotted values are normalized representative functions, not measured operation counts."
}

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