Time vs Space Complexity — Specification¶

Official Documentation Reference

Source: Language standard libraries and algorithm analysis references

Table of Contents¶

1. Docs Reference
2. API / Configuration Reference
3. Core Concepts & Rules
4. Schema / Parameters Reference
5. Behavioral Specification
6. Edge Cases from Official Docs
7. Version & Compatibility Matrix
8. Official Examples
9. Compliance & Best Practices Checklist
10. Related Documentation

1. Docs Reference¶

2. API / Configuration Reference¶

Go: testing.B (Benchmark)¶

func BenchmarkMyAlgo(b *testing.B) {
    data := setup()
    b.ResetTimer()
    for i := 0; i < b.N; i++ {
        myAlgo(data)
    }
}
// Run: go test -bench=. -benchmem

Java: JMH Annotations¶

@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public void benchmarkMyAlgo(MyState state) {
    myAlgo(state.data);
}

Python: timeit Module¶

import timeit
t = timeit.timeit(lambda: my_algo(data), number=1000)
print(f"{t/1000*1000:.3f} ms per call")

Python: sys.getsizeof()¶

import sys
import tracemalloc

tracemalloc.start()
data = list(range(100000))
current, peak = tracemalloc.get_traced_memory()
print(f"Current: {current/1024:.1f} KB, Peak: {peak/1024:.1f} KB")
tracemalloc.stop()

3. Core Concepts & Rules¶

Rule 1: Big-O Describes Growth Rate, Not Actual Time¶

CLRS Chapter 3: "Asymptotic notation characterizes functions according to how fast they grow."

Big-O notation drops constants and lower-order terms. O(2n) = O(n). O(n² + n) = O(n²). This means Big-O is useful for comparing algorithms at large n, but for small n, actual measured time may differ from Big-O predictions.

# O(n) with large constant can be slower than O(n²) for small n
def algo_a(arr):  # O(n) with constant factor 1000
    for _ in range(1000):
        for x in arr: pass

def algo_b(arr):  # O(n²) but small constant
    for i in range(len(arr)):
        for j in range(i+1, len(arr)): pass

# For n < 1000, algo_b may be faster despite worse Big-O

Rule 2: Space Complexity Includes Stack Space¶

CLRS: "We shall generally regard a recursive algorithm that uses space s(n) in addition to the space for the recursion stack as using space s(n)."

Note: Some references count stack space separately. The convention used here counts all memory used, including the call stack. Always clarify which convention you're using.

// O(n) space due to recursion, even though no explicit allocation
func dfs(node *Node) {
    if node == nil { return }
    dfs(node.Left)
    dfs(node.Right)
}

Rule 3: Amortized ≠ Average Case¶

CLRS Chapter 17: "Amortized analysis guarantees the average performance of each operation in the worst case."

Amortized analysis guarantees the total cost over a sequence of operations in the worst case. Average-case analysis assumes a probability distribution over inputs. They are different concepts:

4. Schema / Parameters Reference¶

Complexity Classes Reference¶

Maximum Feasible Input Size (per 1 second)¶

5. Behavioral Specification¶

Normal Operation¶

Time and space complexity describe the asymptotic behavior of algorithms. For a correct complexity analysis:

1. Identify the input size parameter(s): n, V+E, n×m, etc.
2. Count basic operations (comparisons, assignments, arithmetic)
3. Express count as a function of input size
4. Drop constants and lower-order terms
5. Express in Big-O (upper bound), Big-Θ (tight bound), or Big-Ω (lower bound)

Documented Limitations¶

Error / Failure Conditions¶

6. Edge Cases from Official Docs¶

7. Version & Compatibility Matrix¶

Go¶

Java¶

Python¶

8. Official Examples¶

Example 1: Go Benchmark¶

Source: Go testing package

package main

import "testing"

func BenchmarkLinearSearch(b *testing.B) {
    arr := make([]int, 10000)
    for i := range arr { arr[i] = i }
    b.ResetTimer()
    b.ReportAllocs()
    for i := 0; i < b.N; i++ {
        linearSearch(arr, 9999)
    }
}

func linearSearch(arr []int, target int) int {
    for i, v := range arr {
        if v == target { return i }
    }
    return -1
}

Run: go test -bench=BenchmarkLinearSearch -benchmem

Example 2: Python timeit¶

Source: Python timeit docs

import timeit

def linear_search(arr, target):
    for i, v in enumerate(arr):
        if v == target:
            return i
    return -1

arr = list(range(10000))

# Measure time for 1000 runs
t = timeit.timeit(lambda: linear_search(arr, 9999), number=1000)
print(f"Average: {t/1000*1000:.3f} ms per call")

Example 3: Python tracemalloc¶

Source: Python tracemalloc docs

import tracemalloc

tracemalloc.start()

# O(n) space allocation
data = [i ** 2 for i in range(100000)]

current, peak = tracemalloc.get_traced_memory()
print(f"Current: {current / 1024:.1f} KB")
print(f"Peak: {peak / 1024:.1f} KB")

tracemalloc.stop()

9. Compliance & Best Practices Checklist¶

• Algorithm complexity is documented in comments (time AND space)
• Worst-case, average-case, and amortized costs are distinguished
• Stack space from recursion is counted in space analysis
• Benchmarks use proper tools (Go: testing.B, Java: JMH, Python: timeit)
• Memory measurements use language-appropriate tools
• Edge cases (n=0, n=1, large n) are tested
• Trade-off decisions are documented with justification
• Constants and cache effects are considered for performance-critical code

10. Related Documentation¶

Content Rules for specification.md: - Always link directly to the relevant doc section (not just the homepage) - Use official examples from the documentation when available - Note breaking changes and deprecated features between versions - Include official security / safety recommendations - Minimum 2 Core Rules, 3 Parameters, 3 Edge Cases, 2 Official Examples