Space-Time Trade-offs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

def fib_naive(n):
    """
    Naive recursive Fibonacci.
    
    Time: O(2^n) - exponential due to overlapping subproblems
    Space: O(n) - recursion stack depth
    
    fib(5) computes fib(3) twice, fib(2) three times, etc.
    """
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
 
 
def fib_memoized(n, memo=None):
    """
    Memoized Fibonacci: Trade space for time.
    
    Time: O(n) - each value computed once
    Space: O(n) - memo dictionary + recursion stack
    
    The space cost of the memo dictionary eliminates
    exponential redundant computation.
    """
    if memo is None:
        memo = {}
    
    if n in memo:
        return memo[n]  # O(1) lookup instead of O(2^n) recomputation
    
    if n <= 1:
        return n
    
    result = fib_memoized(n - 1, memo) + fib_memoized(n - 2, memo)
    memo[n] = result  # Store for future use
    return result
 
 
# Using Python's built-in memoization
from functools import lru_cache
 
@lru_cache(maxsize=None)  # Unlimited cache
def fib_cached(n):
    """
    LRU-cached Fibonacci.
    
    Same O(n) time, O(n) space as manual memoization.
    Cleaner syntax, handles cache management automatically.
    """
    if n <= 1:
        return n
    return fib_cached(n - 1) + fib_cached(n - 2)
 
 
# Comparison:
# fib_naive(40):    ~30 seconds, 2^40 ≈ 10^12 operations
# fib_memoized(40): ~0.0001 seconds, 40 operations
# Space cost:       ~400 bytes for memo vs near-zero
 
# Trade-off: 400 bytes of memory eliminates billions of operations

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

from functools import lru_cache
 
# Pattern 1: Memoization for combinatorics
@lru_cache(maxsize=None)
def count_paths(m, n):
    """
    Count paths in m×n grid from top-left to bottom-right.
    
    Without memoization: O(2^(m+n)) - exponential
    With memoization: O(m × n) - polynomial
    Space: O(m × n) for cache
    """
    if m == 1 or n == 1:
        return 1
    return count_paths(m - 1, n) + count_paths(m, n - 1)
 
 
# Pattern 2: Memoization with complex keys
def edit_distance(s1, s2):
    """
    Minimum edit distance between strings.
    
    Memoize on (i, j) positions in strings.
    """
    @lru_cache(maxsize=None)
    def dp(i, j):
        if i == 0:
            return j
        if j == 0:
            return i
        
        if s1[i-1] == s2[j-1]:
            return dp(i-1, j-1)
        
        return 1 + min(
            dp(i-1, j),    # Delete
            dp(i, j-1),    # Insert
            dp(i-1, j-1)   # Replace
        )
    
    return dp(len(s1), len(s2))
 
 
# Pattern 3: Bounded memoization for memory control
@lru_cache(maxsize=1000)  # Keep only 1000 most recent
def expensive_api_call(query):
    """
    Cache expensive calls with size limit.
    
    LRU eviction ensures bounded memory while
    still benefiting from temporal locality.
    """
    # Simulate expensive external call
    return external_api.fetch(query)
 
 
# Pattern 4: Memoization with unhashable types
def memoize_list_input():
    """
    For unhashable inputs (lists), convert to hashable form.
    """
    cache = {}
    
    def solve(items):  # items is a list
        key = tuple(items)  # Convert to hashable tuple
        if key in cache:
            return cache[key]
        
        # Expensive computation
        result = heavy_computation(items)
        cache[key] = result
        return result
    
    return solve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

from collections import OrderedDict
 
class LRUCache:
    """
    LRU Cache implementation: O(1) get and put.
    
    Trade-off quantified:
    - Space: O(capacity) for storing entries
    - Time: O(1) for all operations (vs O(computation) without cache)
    - Trade: Each entry uses ~100 bytes; saves potentially seconds of work
    """
    
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()  # Maintains insertion order
    
    def get(self, key):
        """
        Get value if in cache, moving to end (most recent).
        Cache hit: O(1)
        Cache miss: Returns None (caller must compute and put)
        """
        if key not in self.cache:
            return None
        
        # Move to end (most recently used)
        self.cache.move_to_end(key)
        return self.cache[key]
    
    def put(self, key, value):
        """
        Insert or update entry, evicting LRU if at capacity.
        """
        if key in self.cache:
            self.cache.move_to_end(key)
        else:
            if len(self.cache) >= self.capacity:
                # Evict least recently used (first item)
                self.cache.popitem(last=False)
        
        self.cache[key] = value
 
 
class TTLCache:
    """
    Time-based cache: entries expire after TTL seconds.
    
    Useful when data becomes stale, e.g., API responses.
    """
    import time
    
    def __init__(self, ttl_seconds):
        self.ttl = ttl_seconds
        self.cache = {}  # {key: (value, expiry_time)}
    
    def get(self, key):
        if key not in self.cache:
            return None
        
        value, expiry = self.cache[key]
        
        if time.time() > expiry:
            # Entry expired
            del self.cache[key]
            return None
        
        return value
    
    def put(self, key, value):
        import time
        expiry = time.time() + self.ttl
        self.cache[key] = (value, expiry)
 
 
# Application-level caching pattern
def cached_api_call(api_client, cache, cache_key):
    """
    Pattern: Check cache → compute if miss → store result.
    """
    # Try cache first
    cached = cache.get(cache_key)
    if cached is not None:
        return cached  # Cache hit: O(1)
    
    # Cache miss: make expensive call
    result = api_client.expensive_call()  # O(network_latency)
    
    # Store for future use
    cache.put(cache_key, result)
    
    return result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

# Full table approach: O(n) space
def fib_full_table(n):
    """
    Store all Fibonacci numbers up to n.
    
    Time: O(n)
    Space: O(n)
    Benefit: Can query any fib(k) for k <= n after computation
    """
    if n <= 1:
        return n
    
    dp = [0] * (n + 1)
    dp[1] = 1
    
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]
 
 
# Space-optimized: O(1) space
def fib_space_optimized(n):
    """
    Only keep last two values.
    
    Time: O(n) - same as full table
    Space: O(1) - constant, regardless of n
    Trade-off: Can only get fib(n), not intermediate values
    """
    if n <= 1:
        return n
    
    prev2, prev1 = 0, 1
    
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    
    return prev1
 
 
# For n = 1,000,000:
# Full table: ~8 MB (1M integers × 8 bytes)
# Space-optimized: ~16 bytes (2 integers)
# Speed: Nearly identical (marginally faster optimized due to cache locality)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

# Edit Distance: Full 2D table
def edit_distance_full(s1, s2):
    """
    Standard edit distance with full DP table.
    
    Time: O(m × n)
    Space: O(m × n)
    Benefit: Can reconstruct the edit sequence by backtracking
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Base cases
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    # Fill table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    
    return dp[m][n]
 
 
# Edit Distance: Two rows only
def edit_distance_optimized(s1, s2):
    """
    Space-optimized edit distance: only two rows.
    
    Time: O(m × n) - unchanged
    Space: O(n) - reduced from O(m × n)
    Trade-off: Cannot reconstruct the sequence of edits
    """
    m, n = len(s1), len(s2)
    
    # Only need previous row and current row
    prev_row = list(range(n + 1))
    curr_row = [0] * (n + 1)
    
    for i in range(1, m + 1):
        curr_row[0] = i
        
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr_row[j] = prev_row[j-1]
            else:
                curr_row[j] = 1 + min(
                    prev_row[j],      # Delete
                    curr_row[j-1],    # Insert
                    prev_row[j-1]     # Replace
                )
        
        prev_row, curr_row = curr_row, prev_row
    
    return prev_row[n]
 
 
# For s1, s2 with length 10,000 each:
# Full table: 100M cells × 4 bytes = 400 MB
# Optimized: 10K cells × 4 bytes × 2 = 80 KB
# Reduction factor: 5000x memory savings!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

class StreamingStats:
    """
    Compute statistics in O(1) space as data streams in.
    
    Trade-off: Cannot compute median (would need sorted data)
              Cannot answer arbitrary queries about past data
              But can process unlimited data volume
    """
    
    def __init__(self):
        self.count = 0
        self.sum = 0
        self.sum_sq = 0
        self.min_val = float('inf')
        self.max_val = float('-inf')
    
    def update(self, value):
        """Process one value in O(1) time and space."""
        self.count += 1
        self.sum += value
        self.sum_sq += value * value
        self.min_val = min(self.min_val, value)
        self.max_val = max(self.max_val, value)
    
    def mean(self):
        return self.sum / self.count if self.count > 0 else 0
    
    def variance(self):
        if self.count < 2:
            return 0
        mean = self.mean()
        return (self.sum_sq / self.count) - (mean * mean)
    
    def range(self):
        return self.max_val - self.min_val
 
 
# Process a 100GB file with O(1) memory
def process_huge_file(filename):
    stats = StreamingStats()
    
    with open(filename) as f:
        for line in f:
            value = float(line.strip())
            stats.update(value)  # O(1) per line
    
    return stats.mean(), stats.variance()
 
 
class ReservoirSampling:
    """
    Maintain a random sample of k items from a stream.
    
    Problem: Select k random items from a stream of unknown length.
    Cannot store all items, but need uniform random sample.
    
    Space: O(k) regardless of stream length
    """
    
    def __init__(self, k):
        self.k = k
        self.reservoir = []
        self.count = 0
    
    def update(self, item):
        import random
        self.count += 1
        
        if self.count <= self.k:
            # Fill reservoir initially
            self.reservoir.append(item)
        else:
            # Replace with decreasing probability
            j = random.randint(1, self.count)
            if j <= self.k:
                self.reservoir[j - 1] = item
    
    def get_sample(self):
        return self.reservoir
 
 
# Sample 1000 items uniformly from a billion-item stream
def sample_from_huge_dataset(data_iterator, sample_size=1000):
    sampler = ReservoirSampling(sample_size)
    
    for item in data_iterator:
        sampler.update(item)  # O(1) per item
    
    return sampler.get_sample()  # Returns exactly sample_size items

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

# Example: Shortest paths in a graph
 
# PRECOMPUTE: Floyd-Warshall all-pairs
def precompute_all_pairs(graph):
    """
    Compute all-pairs shortest paths upfront.
    
    Precompute: O(V³) time
    Space: O(V²) for distance matrix
    Query: O(1) for any pair
    
    Best when: Many queries, graph doesn't change often
    """
    n = len(graph)
    dist = [[float('inf')] * n for _ in range(n)]
    
    # Initialize from edges
    for u in range(n):
        dist[u][u] = 0
        for v, w in graph[u]:
            dist[u][v] = w
    
    # Floyd-Warshall
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    
    return dist
 
 
# ON-DEMAND: Dijkstra per query
def on_demand_shortest_path(graph, source, target):
    """
    Compute shortest path only when needed.
    
    Precompute: None
    Space: O(V) for single-source distances
    Query: O((V + E) log V) per query (Dijkstra)
    
    Best when: Few queries, graph changes often
    """
    import heapq
    
    dist = {source: 0}
    heap = [(0, source)]
    
    while heap:
        d, u = heapq.heappop(heap)
        
        if u == target:
            return d  # Early termination
        
        if d > dist.get(u, float('inf')):
            continue
        
        for v, w in graph[u]:
            new_dist = d + w
            if new_dist < dist.get(v, float('inf')):
                dist[v] = new_dist
                heapq.heappush(heap, (new_dist, v))
    
    return dist.get(target, float('inf'))
 
 
# HYBRID: Precompute from important nodes only
def precompute_landmark_distances(graph, landmarks):
    """
    Precompute distances from/to k landmark nodes.
    
    Precompute: O(k × (V + E) log V) - k Dijkstras
    Space: O(k × V) - much less than O(V²)
    Query: Use triangle inequality for bounds, Dijkstra for exact
    
    Trade-off: Approximate or selective precomputation
    """
    from_landmark = {}
    to_landmark = {}
    
    for landmark in landmarks:
        from_landmark[landmark] = dijkstra_all(graph, landmark)
        to_landmark[landmark] = dijkstra_all(reverse_graph(graph), landmark)
    
    return from_landmark, to_landmark
 
 
# Analysis for V = 10,000 nodes, E = 50,000 edges:
# 
# Full precompute:
#   Time: O(V³) = 10^12 operations ≈ hours
#   Space: O(V²) = 100M entries = 400 MB
#   Query: O(1)
#
# On-demand:
#   Time: None upfront
#   Space: O(V) per query = 40 KB
#   Query: O((V+E) log V) ≈ 1M operations ≈ 1ms
#
# For 100 queries: On-demand wins (100ms vs hours)
# For 10M queries: Precompute might win (assuming setup amortizes)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

import sys
 
def analyze_tradeoff(n, num_queries):
    """
    Compare hash map vs sorted array for n items, Q queries.
    """
    
    # === APPROACH 1: HASH MAP ===
    # Space: ~64 bytes per entry (key + value + overhead)
    hash_space = n * 64
    
    # Time: O(n) to build, O(1) per query
    hash_build = n  # operations
    hash_query = 1  # operations per query
    hash_total = hash_build + num_queries * hash_query
    
    # === APPROACH 2: SORTED ARRAY ===
    # Space: ~16 bytes per entry (key + value, no overhead)
    array_space = n * 16
    
    # Time: O(n log n) to sort, O(log n) per query
    import math
    array_build = n * math.log2(max(n, 2))  # sort
    array_query = math.log2(max(n, 2))       # binary search per query
    array_total = array_build + num_queries * array_query
    
    print(f"For n={n:,} items, Q={num_queries:,} queries:")
    print(f"  Hash Map:     {hash_space/1e6:.1f} MB, {hash_total/1e6:.1f}M ops")
    print(f"  Sorted Array: {array_space/1e6:.1f} MB, {array_total/1e6:.1f}M ops")
    
    # Break-even analysis
    # hash_total < array_total
    # n + Q < n log n + Q log n
    # Q (1 - log n) < n log n - n
    # For large n, hash map is better when Q is moderate to large
    
    if hash_total < array_total:
        print("  Winner: Hash Map (faster)")
    else:
        print("  Winner: Sorted Array (less memory, acceptable speed)")
 
 
# Example runs:
# analyze_tradeoff(1_000_000, 100)
# For n=1,000,000 items, Q=100 queries:
#   Hash Map:     64.0 MB, 1.0M ops
#   Sorted Array: 16.0 MB, 20.0M ops (sort dominates)
#   Winner: Hash Map (faster)
 
# analyze_tradeoff(1_000_000, 1_000_000)
# For n=1,000,000 items, Q=1,000,000 queries:
#   Hash Map:     64.0 MB, 2.0M ops
#   Sorted Array: 16.0 MB, 40.0M ops
#   Winner: Hash Map (faster despite 4x more memory)
 
# analyze_tradeoff(1_000, 10)
# For n=1,000 items, Q=10 queries:
#   Hash Map:     0.1 MB, 0.001M ops
#   Sorted Array: 0.016 MB, 0.01M ops
#   Winner: Hash Map (both trivial, but hash is faster)