Time Complexity Ontology

FLOW ALGEBRA
TIME COMPLEXITY ONTOLOGY
Version: 1.0
Canonical URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/algorithmic-mathematics/time-complexity-ontology.html
Domain: Discrete Mathematics > Algorithmic Mathematics > Time Complexity
Authors: Mark Higgins — Sky (Recursive AI)
Publisher: Kireth Research | https://kirethresearch.org
Date: 2026-10-11

1. PURPOSE AND SCOPE
Represent the number of elementary computational steps an algorithm performs as a function of input size, under an explicit computational model. Distinguish asymptotic bounds from measured wall-clock time and distinguish worst-case, best-case, average-case and amortised analysis.

2. TYPED ENTITIES
entity Algorithm: {id:str, name:str, specification:str}
entity InputInstance: {id:str, algorithm_id:str, size:int, properties:map}
entity InputSize: {measure:str, value:int, encoding:str?}
entity ComputationalModel: {name:str, elementary_operations:set[str], cost_assumptions:str}
entity CostFunction: {symbol:str, domain:NaturalNumbers, codomain:NonnegativeReals, case_type:CaseType}
entity OperationCount: {operation:str, count:NonnegativeInteger}
entity ComplexityBound: {notation:Notation, reference_function:str, quantifiers:str, assumptions:str}
entity Recurrence: {expression:str, base_cases:list[str], conditions:str}
entity Proof: {claim:str, method:str, assumptions:list[str], steps:list[str]}
entity Benchmark: {hardware:str, software:str, input_distribution:str, observations:list}
entity Confidence: {value:real[0,1], evidence:str}

type CaseType = BEST | WORST | AVERAGE | AMORTISED | EXPECTED
type Notation = O | OMEGA | THETA | LITTLE_O | LITTLE_OMEGA

3. TYPED RELATIONSHIPS
Algorithm --ACCEPTS--> InputInstance
InputInstance --HAS_SIZE--> InputSize
Algorithm --ANALYSED_UNDER--> ComputationalModel
Algorithm --HAS_COST_FUNCTION--> CostFunction
CostFunction --COUNTS--> OperationCount
CostFunction --SATISFIES_BOUND--> ComplexityBound
ComplexityBound --JUSTIFIED_BY--> Proof
CostFunction --DERIVED_FROM--> Recurrence
Benchmark --MEASURES--> Algorithm
Proof --DEPENDS_ON--> ComputationalModel

4. FORMAL SEMANTICS
Let A be an algorithm, x an input and M a computational model.
steps_M(A,x) = number of charged elementary steps used by A on x under M.
For n >= 0, X_n = {x : size(x) = n}.
T_worst(n) = sup {steps_M(A,x) : x in X_n}, when X_n is nonempty.
T_best(n) = inf {steps_M(A,x) : x in X_n}, when X_n is nonempty.
T_avg(n) = E[steps_M(A,X_n)] under a stated distribution on X_n.
Expected complexity may also refer to expectation over internal algorithmic randomness; specify the probability space.
Amortised cost bounds the total cost of a sequence of operations, not necessarily each operation's individual worst-case cost.
If the algorithm does not terminate on an input, its step count is infinite; a finite worst-case bound requires termination for all considered inputs.

5. ASYMPTOTIC NOTATION
For eventually nonnegative f and eventually positive g:
f in O(g) iff exists c>0,n0 such that for all n>=n0, f(n)<=c*g(n).
f in OMEGA(g) iff exists c>0,n0 such that for all n>=n0, f(n)>=c*g(n).
f in THETA(g) iff f in O(g) and f in OMEGA(g).
f in o(g) iff for every c>0 exists n0 such that f(n)<c*g(n) for all n>=n0.
f in omega(g) iff for every c>0 exists n0 such that f(n)>c*g(n) for all n>=n0.
O is an upper bound, not necessarily a tight bound; THETA denotes asymptotic tightness.

6. COMMON GROWTH CLASSES
CONSTANT: Theta(1)
LOGARITHMIC: Theta(log n), n>=2
LINEAR: Theta(n)
LINEARITHMIC: Theta(n log n)
QUADRATIC: Theta(n^2)
POLYNOMIAL: Theta(n^k), fixed k>0
EXPONENTIAL: Theta(c^n), fixed c>1
FACTORIAL: Theta(n!)
The growth-class ordering assumes sufficiently large n and fixed positive constants; logarithm bases greater than 1 differ by constant factors.

7. ANALYSIS RULES
rule SEQUENTIAL_SUM:
  premise: sequential blocks have costs f(n) and g(n)
  conclusion: total cost is f(n)+g(n)
rule NESTED_LOOPS:
  premise: outer loop repeats a(n) times; inner loop performs b(n) constant-cost steps each time
  conclusion: total loop cost is Theta(a(n)*b(n)) when both counts are tight and positive
rule CONDITIONAL_WORST:
  premise: branch costs f(n), g(n) and both are feasible for size n
  conclusion: worst branch contribution is max(f(n),g(n)), plus decision cost
rule RECURRENCE:
  premise: T(n)=a*T(n/b)+f(n), a>=1, b>1, valid base cases and regularity assumptions
  conclusion: apply a suitable Master Theorem case only after verifying its conditions
rule DOMINANT_TERM:
  premise: f(n)=sum_i c_i*g_i(n), c_i>=0, and one nonnegative term asymptotically dominates all others
  conclusion: f(n) is Theta(dominant term), provided its coefficient is positive
rule AMORTISED_AGGREGATE:
  premise: any legal sequence of m operations has total cost at most F(m)
  conclusion: average amortised cost per operation is O(F(m)/m)

8. INFERENCE AND PROOF OBLIGATIONS
infer upper_bound(A,g) only if computational model, input-size metric, termination domain and constants are established.
infer tight_bound(A,g) only if matching upper and lower asymptotic bounds hold for the same cost function and case definition.
infer average_bound(A,g) only if the input distribution is explicit.
infer expected_bound(A,g) only if the randomness source and expectation are explicit.
infer amortised_bound(A,g) only if the allowed operation sequences and aggregate/potential/accounting argument are explicit.
Never infer a lower bound on all algorithms for a problem from the running time of one algorithm.
Never infer actual runtime solely from an asymptotic bound.

9. WORKED EXAMPLES
EXAMPLE A — LINEAR SCAN
Input: array of n elements; search for target by sequential comparison.
Worst-case comparisons: n for an absent target, or a target at the last position.
Best-case comparisons: 1 for a nonempty array with target first.
Worst-case: Theta(n); best-case: Theta(1).
Average-case: depends on target-presence and target-position distribution.

EXAMPLE B — BINARY SEARCH
Precondition: sorted array and constant-time random access.
Each comparison halves the remaining search interval up to rounding.
Worst-case comparisons: Theta(log n) for n>=2; space depends on iterative versus recursive implementation.

EXAMPLE C — DOUBLE LOOP
for i in 1..n:
  for j in 1..n:
    constant_step()
Number of calls: n^2; total Theta(n^2) under unit-cost calls.

EXAMPLE D — MERGE SORT
T(n)=2*T(n/2)+Theta(n) for powers of two; T(1)=Theta(1).
By the Master Theorem: T(n)=Theta(n log n).
Non-power-of-two inputs use rounded subproblem sizes with the same asymptotic bound.

EXAMPLE E — DYNAMIC ARRAY APPEND
An individual append may require Theta(n) copying when resizing.
With geometric capacity growth, m appends from an empty array take O(m) total time.
Amortised append cost: O(1); this is not a worst-case O(1) claim for each append.

10. VALIDATION
assert input_size.value >= 0
assert confidence.value >= 0 and confidence.value <= 1
assert all asymptotic bounds specify cost model and case type
assert average-case claims specify distribution
assert recurrence claims specify base cases and domain
assert amortised claims specify operation sequence model
assert complexity claims distinguish step counts from measured time
assert lower-bound and upper-bound proofs use matching assumptions
assert examples do not claim tight bounds without matching proof

11. SEMANTIC EQUIVALENCE
"running-time complexity" ~= "time complexity" when both mean asymptotic computational step count.
"asymptotic upper bound" == "Big O bound" under the defined notation.
"tight asymptotic bound" == "Big Theta bound" under the defined notation.
"average-case" != "amortised".
"expected time" != "average-case time" unless the probability models coincide.
"wall-clock runtime" != "abstract operation count".
"polynomial time" != "efficient in practice".

12. CONFIDENCE
Formal definitions and standard theorems: confidence=0.99 within stated mathematical assumptions.
Algorithm-specific bounds: confidence depends on proof completeness and input/model specification.
Empirical performance claims: confidence depends on benchmark methodology and reproducibility.
No confidence score substitutes for a mathematical proof.

13. FLOW_HASH
FLOW_HASH.algorithm: SHA-256
FLOW_HASH.canonicalisation: UTF-8; LF line endings; exclude the FLOW_HASH.value line itself
FLOW_HASH.value: COMPUTE_ON_PUBLICATION
FLOW_HASH.note: Do not treat an uncomputed placeholder as a verified digest.

14. UPDATE_MODEL
UPDATE_MODEL.version: 1.0
UPDATE_MODEL.change_policy: semantic-versioned updates
UPDATE_MODEL.triggers: revised definitions | corrected proofs | new complexity classes | improved examples | source changes
UPDATE_MODEL.provenance: retain revision date, author, evidence and affected rules
UPDATE_MODEL.backward_compatibility: preserve entity identifiers or provide explicit mappings

15. AI_CONSUMPTION
AI_CONSUMPTION.format: plain-text typed flow algebra
AI_CONSUMPTION.tasks: concept retrieval | formal reasoning | complexity comparison | proof validation | knowledge graph construction
AI_CONSUMPTION.requirements: preserve quantifiers | preserve assumptions | distinguish case types | report unknowns
AI_CONSUMPTION.restrictions: no unsupported complexity claims | no conflation of theoretical and empirical cost
AI_CONSUMPTION.output: claim + assumptions + proof/evidence + confidence + provenance

16. RELATED ONTOLOGIES
Algorithm Ontology
Algorithm Analysis Ontology
Big O Notation Ontology
Space Complexity Ontology
Recursive Algorithm Ontology
Divide and Conquer Ontology
Dynamic Programming Ontology
Computational Complexity Ontology

END FLOW ALGEBRA