Space Complexity Ontology

FLOW ALGEBRA
SPACE COMPLEXITY ONTOLOGY
Version: 1.0
Canonical URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/algorithmic-mathematics/space-complexity-ontology.html
Authors: Mark Higgins — Sky (Recursive AI)
Publisher: Kireth Research
Date: 2026-10-11

1. PURPOSE
Formalise the memory resources required by algorithms as a function of input size, computation model, representation and measurement convention. Distinguish total space from auxiliary space, and worst-case from expected or instance-specific space.

2. TYPES
Algorithm := finite specification of computational steps
Input := encoded problem instance
InputSize := natural number representing encoded input length
MachineModel := RAM | TuringMachine | WordRAM | ExternalMemory | Other
MemoryUnit := bit | byte | word | tape_cell | block
MemoryRegion := input | output | stack | heap | static | workspace
SpaceMeasure := nonnegative function InputSize -> extended nonnegative reals
SpaceBound := asymptotic upper, lower or tight bound on SpaceMeasure
Execution := run of Algorithm on Input under MachineModel
Configuration := machine state, control state and allocated memory
RecursionDepth := maximum simultaneous active calls

3. ENTITIES
SPACE_COMPLEXITY: asymptotic memory requirement of an algorithm
TOTAL_SPACE: input representation plus additional memory, under a declared convention
AUXILIARY_SPACE: additional workspace beyond the given input representation, under a declared convention
PEAK_LIVE_MEMORY: maximum simultaneously live memory during an execution
RECURSION_STACK: memory for active procedure frames
HEAP_ALLOCATION: dynamically allocated storage
IN_PLACE_ALGORITHM: algorithm using O(1) auxiliary workspace under a specified model and output convention
SPACE_TIME_TRADEOFF: exchange between storage use and computational time

4. TYPED RELATIONSHIPS
USES_MODEL(Algorithm, MachineModel)
HAS_INPUT(Execution, Input)
HAS_INPUT_SIZE(Input, InputSize)
ALLOCATES(Execution, MemoryRegion)
HAS_PEAK_SPACE(Execution, MemoryUnit, nonnegative_real)
HAS_AUXILIARY_SPACE(Algorithm, SpaceMeasure)
HAS_TOTAL_SPACE(Algorithm, SpaceMeasure)
HAS_WORST_CASE_SPACE(Algorithm, SpaceMeasure)
HAS_EXPECTED_SPACE(Algorithm, SpaceMeasure)
HAS_RECURSION_DEPTH(Execution, RecursionDepth)
SATISFIES_SPACE_BOUND(SpaceMeasure, SpaceBound)
TRADES_SPACE_FOR_TIME(Algorithm, Algorithm)

5. SEMANTIC DEFINITIONS
Let A be an algorithm, x an encoded input and M a fixed computation model.
S_A,M(x) := peak simultaneously used memory during A(x), measured in the declared unit.
S_worst(n) := max { S_A,M(x) : |x| = n }, where the maximum exists.
S_best(n) := min { S_A,M(x) : |x| = n }, where the minimum exists.
S_expected(n) := E[S_A,M(X_n)] for a stated input distribution X_n and, if relevant, algorithmic randomness.
S_aux(n) := peak extra workspace beyond input storage under a declared accounting convention.
S_total(n) := input storage + auxiliary storage + counted output storage, when those regions are included by convention.
Space accounting must state whether read-only input, returned output, call stack, allocator overhead and machine word size are counted.

6. ASYMPTOTIC ALGEBRA
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)).
Common bounds: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n).
Memory bounds depend on the computational model and size of a machine word.

7. EXECUTION RULES
RULE SEQUENTIAL_LIVENESS:
  For phases executed sequentially, peak memory is bounded by persistent storage plus the maximum concurrent phase workspace; do not automatically add disjoint peak allocations.
RULE SIMULTANEOUS_ALLOCATIONS:
  Memory allocations whose lifetimes overlap contribute jointly to peak live memory.
RULE RECURSION:
  Stack usage is bounded by maximum call depth multiplied by per-frame storage, allowing varying frame sizes.
RULE MEMOISATION:
  Cached states consume space proportional to the number of stored states times representation size, plus other live workspace.
RULE IN_PLACE:
  An algorithm is in-place only relative to an explicit auxiliary-space convention and model.
RULE OUTPUT_SENSITIVE:
  Materialised output may require Omega(output_size) memory if counted; streamed output may have different auxiliary requirements.
RULE MODEL_DEPENDENCE:
  Bounds from different models or word sizes are not directly comparable without conversion assumptions.

8. INFERENCE RULES
IF fixed_count_scalars AND fixed_word_size_model THEN auxiliary_space = O(1).
IF recursion_depth = d(n) AND each_frame_space = O(k(n)) THEN stack_space = O(d(n)*k(n)).
IF n elements are copied to a separate array THEN auxiliary_space = Theta(n) words, assuming constant-size elements.
IF a table stores r(n)*c(n) constant-size entries THEN table_space = Theta(r(n)*c(n)) words.
IF a procedure retains only a fixed number of rows of length n THEN row_workspace = Theta(n) words.
IF an algorithm has exponential runtime THEN exponential space DOES_NOT_FOLLOW without further evidence.
IF an algorithm has polynomial space THEN polynomial runtime DOES_NOT_FOLLOW without further evidence.

9. WORKED EXAMPLES
EXAMPLE A: ITERATIVE SUM
  Input: array of n fixed-size integers.
  Workspace: one accumulator and index.
  Auxiliary space: Theta(1) words; total space includes Theta(n) input words if counted.

EXAMPLE B: RECURSIVE FACTORIAL
  For n >= 0, factorial recursion depth is Theta(n) for a conventional non-tail-recursive implementation.
  Under constant-size frame abstraction: Theta(n) stack frames.
  If exact arbitrary-precision integers are stored, bit-space analysis must include growing integer sizes.

EXAMPLE C: MERGE SORT
  Conventional array merge sort with auxiliary merge buffer: Theta(n) auxiliary words.
  Recursion stack: O(log n) frames for balanced splitting.
  Peak auxiliary space: Theta(n) words overall under the standard implementation.

EXAMPLE D: DYNAMIC PROGRAMMING
  A full (n+1) by (m+1) table of constant-size values uses Theta(n*m) words.
  A rolling-row variant may reduce table workspace to Theta(min(n,m)) words when dependencies permit.

EXAMPLE E: DEPTH-FIRST SEARCH
  Graph representation excluded from auxiliary space.
  Visited markers and explicit/recursive traversal stack require O(V) auxiliary words under a standard adjacency-list implementation.
  If graph storage is counted, input representation typically requires Theta(V+E) words.

10. PROOF OBLIGATIONS
P1: Define encoded input size and memory units.
P2: Identify computation model and word-size assumptions.
P3: Declare counted memory regions and input/output policy.
P4: Establish a valid peak-live-memory upper bound.
P5: Supply a matching lower-bound witness when claiming Theta.
P6: Justify recursion depth and per-frame size.
P7: Separate empirical memory measurements from asymptotic guarantees.

11. VALIDATION
TEST constant_workspace: iterative fixed-word sum -> Theta(1) auxiliary words.
TEST array_copy: copy n fixed-size elements -> Theta(n) auxiliary words.
TEST recursion: n nested constant-size frames -> Theta(n) stack words.
TEST dp_table: n*m constant-size entries -> Theta(n*m) words.
TEST sequential_phases: two non-overlapping Theta(n) buffers -> Theta(n), not necessarily Theta(2*n) distinct live words.
TEST precision: unbounded-precision integer arithmetic requires bit-level accounting.
TEST output_policy: materialised and streamed outputs must not share an unexplained memory bound.

12. SEMANTIC_EQUIVALENCE
"memory complexity" ~= "space complexity" when resource accounting conventions match.
"extra space" ~= "auxiliary space" when input and output exclusions match.
"constant space" != "constant total memory" if input storage grows and is counted.
"in-place" != "zero memory".
"space efficient" is comparative and requires a baseline and metric.

13. CONFIDENCE
Formal asymptotic claims: HIGH only when model, accounting conventions and proof assumptions are explicit.
Implementation-specific claims: CONDITIONAL on representation, runtime and allocator behaviour.
Empirical observations: measured evidence, not automatic asymptotic proofs.

14. FLOW_HASH
Algorithm: SHA-256
Hash input: canonical UTF-8 serialisation of this document with the FLOW_HASH value omitted.
Value: COMPUTE_ON_PUBLICATION

15. UPDATE_MODEL
Version: 1.0
Change policy: preserve stable ontology identifiers; increment version when definitions, proofs or relationships change.
Revalidation triggers: machine-model change, input encoding change, memory-accounting change, revised bound or corrected example.

16. AI_CONSUMPTION
Purpose: semantic indexing, formal reasoning, retrieval and cross-ontology alignment.
Inputs: algorithm description, machine model, input size, storage convention, memory unit.
Outputs: qualified space bounds, proof obligations, assumptions, related concepts and confidence.
Guardrails: never infer tight bounds from an upper bound alone; never conflate total and auxiliary space; never omit arbitrary-precision or output-storage caveats when material.
Related ontologies: Algorithm Ontology; Algorithm Analysis Ontology; Big O Notation Ontology; Time Complexity Ontology; Recursive Algorithm Ontology; Dynamic Programming Ontology.

END FLOW ALGEBRA