Algorithm Analysis Ontology

FLOW ALGEBRA
ALGORITHM ANALYSIS ONTOLOGY
Version: 1.0
Source: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/algorithmic-mathematics/algorithm-analysis-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Project: Kireth Semantic Library
Date: 2026-10-11

1. PURPOSE AND SCOPE
Model the formal analysis of algorithms: resource usage, correctness, asymptotic behaviour, input sensitivity, recurrence solving, and empirical validation. Distinguish mathematical guarantees from observed benchmarks.

2. TYPED ENTITIES
Algorithm: computational procedure mapping valid inputs to outputs.
Problem: specification of admissible inputs and required outputs.
InputInstance: concrete input with measurable size and structure.
InputSize: non-negative integer n defined by a declared size measure.
CostModel: rules assigning costs to primitive operations and resources.
OperationCount: count of specified primitive operations.
TimeComplexity: function bounding time cost relative to input size.
SpaceComplexity: function bounding memory usage relative to input size.
AuxiliarySpace: extra working storage excluding the input; output inclusion must be declared.
WorstCase: maximum cost over inputs of size n.
BestCase: minimum cost over inputs of size n.
AverageCase: expected cost under an explicitly defined input distribution.
AmortisedCost: average cost per operation over a sequence, bounded for all allowed sequences.
AsymptoticBound: O, Omega, or Theta comparison between non-negative functions.
RecurrenceRelation: equation expressing a cost function in terms of smaller arguments.
Invariant: predicate preserved at designated program points.
TerminationMeasure: well-founded quantity that strictly decreases on recursive or iterative progress.
ComplexityClass: class of problems defined by resource-bounded computation, distinct from a single algorithm's cost.
Benchmark: observed performance under a specified environment and workload.

3. RELATIONSHIP TYPES
SOLVES(Algorithm, Problem)
ACCEPTS(Algorithm, InputInstance)
HAS_SIZE(InputInstance, InputSize)
USES_MODEL(Algorithm, CostModel)
COUNTS(CostModel, OperationCount)
HAS_TIME_COST(Algorithm, TimeComplexity)
HAS_SPACE_COST(Algorithm, SpaceComplexity)
HAS_RECURRENCE(Algorithm, RecurrenceRelation)
MAINTAINS(Algorithm, Invariant)
TERMINATES_BY(Algorithm, TerminationMeasure)
HAS_BOUND(TimeComplexity | SpaceComplexity, AsymptoticBound)
MEASURED_BY(Algorithm, Benchmark)
DEPENDS_ON(CostEstimate, InputDistribution | HardwareEnvironment | Implementation)

4. FORMAL SEMANTICS
Let I_n = {x in Domain(A) : size(x) = n}.
Let C_A(x; M) >= 0 be the cost of algorithm A on input x under cost model M.
T_worst(n) = sup {C_A(x; M) : x in I_n}, when I_n is nonempty.
T_best(n)  = inf {C_A(x; M) : x in I_n}, when I_n is nonempty.
T_avg(n)   = E_{x ~ D_n}[C_A(x; M)] for declared probability distribution D_n.
If I_n is empty, worst/best costs at n are undefined unless an explicit convention is supplied.

For eventually non-negative f and g:
f(n) in O(g(n)) iff exists c > 0, n0 such that 0 <= f(n) <= c*g(n) for all n >= n0.
f(n) in Omega(g(n)) iff exists c > 0, n0 such that 0 <= c*g(n) <= f(n) for all n >= n0.
f(n) in Theta(g(n)) iff f(n) in O(g(n)) and f(n) in Omega(g(n)).
f(n) in o(g(n)) iff for every c > 0, eventually 0 <= f(n) < c*g(n).
f(n) in omega(g(n)) iff for every c > 0, eventually 0 <= c*g(n) < f(n).

5. ANALYSIS PIPELINE
flow AlgorithmAnalysis(A, P, M, S, D?):
  REQUIRE SOLVES(A, P)
  DEFINE input domain and size measure S
  DEFINE operation and memory accounting under M
  DERIVE cost expression or recurrence from algorithm structure
  PROVE bounds under stated assumptions
  CLASSIFY worst and best cases; average only when D is supplied
  ESTABLISH partial correctness via specification and invariants
  ESTABLISH termination independently via a well-founded argument
  VALIDATE small cases and boundary conditions
  RECORD implementation-dependent measurements separately
  EMIT analysis record with provenance, confidence and limitations

6. INFERENCE RULES
R1: f in O(g) AND g in O(h) => f in O(h), for compatible eventual non-negative functions.
R2: f in Theta(g) => f in O(g) AND f in Omega(g).
R3: f in O(g) AND h in O(k) => f+h in O(g+k), with eventual non-negative functions.
R4: For constant a>0, a*f in Theta(f) when f is eventually positive.
R5: If a loop runs at most n times and each iteration costs at most O(1), loop cost is O(n), excluding separately counted setup.
R6: For disjoint sequential phases with costs T1 and T2, total cost T1+T2 under an additive cost model.
R7: A valid loop invariant plus termination and the correct postcondition implies total correctness for the loop.
R8: Empirical timing alone DOES NOT imply a proven asymptotic bound.
R9: Worst-case upper bound DOES NOT imply matching lower bound.
R10: A lower bound on a problem DOES NOT automatically establish the cost of every algorithm solving it without a matching model and quantifiers.

7. RECURRENCE ANALYSIS
Example: T(n) = 2*T(n/2) + Theta(n), n powers of two, T(1)=Theta(1).
Under standard regularity assumptions, T(n)=Theta(n log n).
Example: T(n) = T(n-1) + Theta(1), n>=2, T(1)=Theta(1) => Theta(n).
Master Theorem requires a recurrence of the appropriate form and its case conditions; it is not universally applicable.

8. WORKED EXAMPLES
Linear search on array of n elements, unit-cost comparisons:
  Worst-case comparisons = n for n>=1.
  Best-case comparisons = 1 for n>=1 if target appears at first position.
  Average-case depends on hit probability and target-position distribution.
Binary search on sorted random-access array:
  Worst-case comparison count is O(log n) under a unit-cost comparison model.
  Requires sorted input and valid index arithmetic.
Insertion sort:
  Worst-case time Theta(n^2) comparisons/shifts in a standard array implementation.
  Best-case time Theta(n) on already sorted input in the usual implementation.
Merge sort:
  Standard recurrence 2*T(n/2)+Theta(n) gives Theta(n log n) time.
  Auxiliary space is typically Theta(n) for a conventional array-based merge implementation; implementation choices matter.

9. CORRECTNESS AND TERMINATION
Partial correctness: if the algorithm terminates, its result meets the specification.
Termination: every valid execution finishes, supported by a well-founded descent or other proof.
Total correctness = partial correctness + termination.
Complexity statements must specify whether pathological or invalid inputs are excluded.

10. SPACE AND RESOURCE ACCOUNTING
Report peak live memory, not total allocated bytes over time, unless specified.
Separate input storage, output storage, recursion stack, and auxiliary workspace.
State whether arithmetic on arbitrarily large integers is unit-cost or bit-cost.
For parallel algorithms, distinguish work, span, communication, and memory usage.

11. SEMANTIC EQUIVALENCE
'Running time' ~ 'time cost' only when the same model and metric are intended.
'Big O' != 'exact running time'.
'Average case' != 'amortised analysis'.
'Worst case' != 'typical case'.
'Algorithm analysis' != 'experimental benchmarking'.
'Polynomial time' is model-dependent and requires explicit input encoding/size.

12. VALIDATION RULES
V1: Every cost claim names the input-size parameter.
V2: Every complexity bound identifies resource, case, and cost model.
V3: Expected costs require a declared probability distribution.
V4: Recurrence solutions include base conditions and domain restrictions.
V5: Correctness claims identify preconditions and postconditions.
V6: Empirical claims report machine, compiler/runtime, data, repetitions, and uncertainty where available.
V7: Exclude unsupported claims of optimality; prove lower bounds before asserting asymptotic optimality.
V8: Keep proved bounds distinct from heuristic estimates.

13. CONFIDENCE
Formal theorem with verified assumptions: HIGH.
Hand-derived bound with checked reasoning: MODERATE_TO_HIGH.
Empirical estimate across documented workloads: CONTEXT_DEPENDENT.
Unspecified implementation or distribution: LOW / INCOMPLETE.
Confidence is evidence-qualified metadata, not a mathematical probability of truth.

14. FLOW HASH AND PROVENANCE
FLOW_ID: discrete-mathematics.algorithmic-mathematics.algorithm-analysis-ontology
FLOW_VERSION: 1.0
CANONICAL_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/algorithmic-mathematics/algorithm-analysis-ontology.html
FLOW_HASH: COMPUTE_SHA256_FROM_CANONICAL_UTF8_CONTENT_AT_PUBLICATION
HASH_STATUS: PENDING_COMPUTATION
PROVENANCE: Kireth Semantic Library; authored Flow Algebra companion.

15. UPDATE MODEL
On revision: increment version; retain prior immutable snapshot; recompute SHA-256; record timestamp, change summary, and affected definitions; revalidate examples and inference rules.

16. AI CONSUMPTION
INPUT: algorithm pseudocode, problem specification, size measure, cost model, optional distribution.
OUTPUT: typed complexity claims, proofs, assumptions, examples, provenance, confidence.
REASONING_MODE: symbolic derivation + proof checking + empirical corroboration.
GUARDRAILS: no invented measurements; no average-case claim without distribution; no conflation of Big O with tight bounds.

END FLOW ALGEBRA