Time Complexity Comparator for Sorting Algorithms

Inspectable records

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

Ledger rows

1

No ledger note is attached.

Review findings

No outright mathematical contradiction is present in the listed concept, but the instrument is not fully deterministic as specified. Add explicit algorithm variants, radix parameters, average-case assumptions, space convention, input validation, and a precise plot/cost model before marking PASS.

Formula and scope findings

• The lookup-table approach is valid only after defining the exact variant of each algorithm. Bubble sort must specify whether an early-exit optimization is used; best-case complexity is O(n) with early exit but O(n^2) without it.
• Quick-sort space complexity depends on recursion-stack policy, partition scheme, and worst-case stack protection. O(log n) average space and O(n) worst-case space are standard for recursive quicksort, but an implementation with tail-recursion elimination or an explicit stack may differ.
• Radix-sort complexity cannot be represented solely as a function of n. It requires the number of digit passes d and radix/base b; a standard bound is O(d(n+b)) time and O(n+b) auxiliary space for stable counting-sort passes.
• The optional live comparison count is not defined: the input array, sorting implementation, comparison-counting convention, and treatment of swaps/moves are unspecified. A complexity class cannot produce an exact operation-count plot without a chosen cost model.
• Big-O classes do not determine exact plotted y-values. The spec must define whether the plot uses representative functions such as n, n log2(n), and n^2, measured operation counts, or another normalization.
• The phrase 'average case' is ambiguous unless the input distribution and pivot-selection policy are specified, especially for quicksort.

Unit assumptions

• n is a dimensionless count of array elements and must be an integer with n >= 0; actual sorting normally requires n >= 1, while n = 0 is an empty-array edge case.
• For logarithmic representative curves, the log base is irrelevant to asymptotic class but must be specified for numeric plots; the test vectors use log2.
• The standard merge-sort space result assumes an array implementation using O(n) auxiliary storage.
• The quicksort result assumes recursive in-place partitioning, average recursion depth O(log n), and worst-case recursion depth O(n).
• The bubble-sort result assumes the usual early-exit flag optimization.
• The radix-sort result assumes base b >= 2, d digit passes, and stable counting-sort passes; its numeric work model is d(n+b).

Boundary hardening

BREAK_CLAIMED · SELF_FLAGGED

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.

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

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