Algorithm complexity documentation inconsistency across languages

Recommended standard

Adopt a single, machine-readable complexity schema stored centrally (for example, complexity.yaml or complexity.json) and require every language-specific README or docstring to reference it by algorithm ID instead of restating numbers. Each entry should specify:

• Algorithm variant (for example, randomized QuickSort versus deterministic pivot, or Dijkstra with binary heap versus Fibonacci heap).
• Worst-case, average-case, and best-case time in Big O.
• Auxiliary space and total space in Big O.
• Input model and assumptions (comparison-based RAM model, distinct keys, random pivot, defined input distribution for average-case claims).

Likely explanation versus confirmed facts

The likely explanation is organizational: each language folder is maintained independently, so one contributor may document worst-case QuickSort as O(n^2) while another documents average-case as O(n log n), and notation styles differ by folder. The confirmed fact is that Big O class is language-independent under the standard RAM model for the same algorithm; Python, Java, and C++ change constant factors, cache behavior, and garbage-collection pauses, not the asymptotic class. The bound changes only when the implementation itself changes (for example, C++ std::sort is introsort, not QuickSort, so its documented worst-case bound differs).

Steps to synchronize and verify

1. Create the central schema and map every implemented algorithm to one entry.
2. Replace inline complexity numbers in language READMEs with a reference to the schema ID; keep only a short summary if needed.
3. Add a CI check that parses the schema and flags missing or mismatched entries in pull requests touching algorithm documentation. If CI is not available, use a code-review checklist instead.
4. Verify empirically with operation counts, not wall-clock time. Instrument comparisons, swaps, or edge relaxations across input sizes n, 2n, 4n, 8n, regress log(operations) against log(n), and compare the slope to the documented bound. Use random and adversarial inputs, report the median over at least 30 trials after warm-up, and control the environment (single thread, fixed CPU governor, repeated trials).

Safe inspection command

grep -R "O(" --include="*.py" --include="*.java" --include="*.cpp" .

This only locates existing claims; it does not verify them.

Assumptions and uncertainty

• This guidance assumes the standard RAM model and comparison-based inputs.
• Average-case complexity is undefined without a specified input distribution; mark such entries for review until one is defined.
• Wall-clock timing alone cannot verify Big O because startup, JIT, garbage collection, and system load dominate at small sizes.
• Tail-call elimination, lazy evaluation, and language-specific optimizations may alter space behavior and are not guaranteed across implementations.

If you can share whether the repository enforces CI gating on documentation changes, I can narrow the enforcement step to CI or code review.