Source: https://guthlabs.ai/docs/instruments/time-complexity-comparator-for-sorting-algorithms/
instrument / verified-clean
# Time Complexity Comparator for Sorting Algorithms
The current ledger marks this instrument verified clean within the source-bound verification corpus.
Status: **VERIFIED_CLEAN**Lifecycle: **verified-clean**
## Inspectable records
[01**Overview**Purpose and lifecycle]()[02**Mechanism**Method and assumptions]()[03**Implementation**Binding and validation]()[04**Qualification**Evidence and errata]()
## 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`