Time Complexity Comparator for Sorting Algorithms mechanism

Model scope

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.

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

Units and conventions

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

Inspectable vector

One of 4 source-bound review vectors:

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

Failure boundary

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.

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
• BOUNDARY_HAZARD_CATALOG.json