Space Complexity Analysis

This guide covers space complexity analysis, memory usage patterns, and how to analyze algorithm memory efficiency across different programming languages.

🎯 What is Space Complexity?

Space complexity measures how the memory usage of an algorithm grows as the input size increases. It helps us understand memory requirements and optimize for memory-constrained environments.

Space Complexity Notation

• O(1): Constant space - memory usage doesn't depend on input size
• O(log n): Logarithmic space - grows very slowly
• O(n): Linear space - grows proportionally with input size
• O(n log n): Linearithmic space - common in efficient sorting
• O(n²): Quadratic space - grows quickly, common in nested data structures

🔧 Space Complexity Examples

O(1) - Constant Space

Temporary Variables

Using a few additional variables (like a temp for swapping or a counter for a loop) consumes a fixed amount of memory regardless of the input size. This is the definition of O(1) space complexity.

# Swapping two variables
def swap(a, b):
    temp = a  # One extra variable
    a = b
    b = temp
    return a, b

# Finding maximum
def find_max(arr):
    max_val = arr[0]  # One extra variable
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val

O(n) - Linear Space

# Creating a copy of array
def reverse_array(arr):
    reversed_arr = []  # O(n) space
    for i in range(len(arr)-1, -1, -1):
        reversed_arr.append(arr[i])
    return reversed_arr

# Recursive factorial (call stack)
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n-1)  # O(n) call stack space

O(n²) - Quadratic Space

# Creating all pairs
def all_pairs(arr):
    pairs = []  # O(n²) space
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            pairs.append((arr[i], arr[j]))
    return pairs

# Adjacency matrix for graph
def create_adjacency_matrix(n):
    matrix = [[0] * n for _ in range(n)]  # O(n²) space
    return matrix

📊 Memory Usage Comparison

Input Size	O(1)	O(log n)	O(n)	O(n log n)	O(n²)
10	1	4	10	33	100
100	1	7	100	664	10,000
1,000	1	10	1,000	9,966	1,000,000
10,000	1	13	10,000	132,877	100,000,000

🎯 Language-Specific Memory Analysis

Java Memory

// Primitive types - fixed size
int num = 42;  // 4 bytes
double value = 3.14;  // 8 bytes
boolean flag = true;  // 1 byte

// Objects - overhead + fields
String str = "Hello";  // ~12 bytes + overhead
ArrayList<Integer> list = new ArrayList<>();  // Dynamic, grows as needed

// Memory estimation
public class MemoryExample {
    public static void main(String[] args) {
        Runtime runtime = Runtime.getRuntime();
        long usedMemory = runtime.totalMemory() - runtime.freeMemory();

        int[] array = new int[1000000];  // ~4MB
        long newUsedMemory = runtime.totalMemory() - runtime.freeMemory();

        System.out.println("Memory used: " + (newUsedMemory - usedMemory) + " bytes");
    }
}

Python Memory

import sys

# Check object size
def get_size(obj):
    return sys.getsizeof(obj)

# Lists have overhead
my_list = [1, 2, 3, 4, 5]
print(f"List size: {get_size(my_list)} bytes")  # ~120 bytes

# Dictionaries have more overhead
my_dict = {"a": 1, "b": 2, "c": 3}
print(f"Dict size: {get_size(my_dict)} bytes")  # ~360 bytes

# Strings are objects
my_string = "Hello, World!"
print(f"String size: {get_size(my_string)} bytes")  # ~50 bytes

C Memory

#include <stdio.h>
#include <stdlib.h>

// Manual memory management
int* create_array(int size) {
    int* array = (int*)malloc(size * sizeof(int));
    if (array == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }
    return array;
}

// Memory usage tracking
void check_memory_usage() {
    // Platform-specific memory checking
    #ifdef __linux__
        FILE* status = fopen("/proc/self/status", "r");
        // Parse memory information
        fclose(status);
    #endif
}

🚀 Memory Optimization Strategies

In-Place Operations

# Bad: O(n) extra space
def reverse_array_extra(arr):
    reversed_arr = []  # O(n) space
    for i in range(len(arr)-1, -1, -1):
        reversed_arr.append(arr[i])
    return reversed_arr

# Good: O(1) extra space
def reverse_array_inplace(arr):
    left, right = 0, len(arr) - 1
    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1
    return arr

Generator Usage

# Bad: O(n) space for large dataset
def process_large_file_bad(filename):
    with open(filename, 'r') as file:
        lines = file.readlines()  # Loads entire file
    return [line.strip() for line in lines]

# Good: O(1) space using generator
def process_large_file_good(filename):
    with open(filename, 'r') as file:
        for line in file:  # Process one line at a time
            yield line.strip()  # Generator, memory efficient

Memory Pool Pattern

// Bad: Creating many objects
public class BadExample {
    public void processItems(List<Item> items) {
        for (Item item : items) {
            ProcessedItem processed = new ProcessedItem(item);  // Many objects
            process(processed);
        }
    }
}

// Good: Reusing objects
public class GoodExample {
    private ProcessedItem reusableItem = new ProcessedItem();

    public void processItems(List<Item> items) {
        for (Item item : items) {
            reusableItem.reset(item);  // Reuse object
            process(reusableItem);
        }
    }
}

Efficient Data Structures

# Bad: List for frequent lookups
user_permissions_list = [("alice", ["read", "write"]), ("bob", ["read"])]
def has_permission(username, permission):
    for user, perms in user_permissions_list:  # O(n)
        if user == username:
            return permission in perms
    return False

# Good: Dictionary for O(1) lookups
user_permissions_dict = {
    "alice": {"read", "write"},
    "bob": {"read"}
}
def has_permission_optimized(username, permission):
    return permission in user_permissions_dict.get(username, set())  # O(1)

🛠️ Memory Profiling

Java Profiling

// Using VisualVM or JConsole
// 1. Run application with: java -XX:+PrintGCDetails -XX:+PrintGCTimeStamps
// 2. Connect VisualVM: jvisualvm
// 3. Monitor heap usage, garbage collection, and object creation

// Programmatic memory checking
public class MemoryProfiler {
    public static void logMemoryUsage(String label) {
        Runtime runtime = Runtime.getRuntime();
        long totalMemory = runtime.totalMemory();
        long freeMemory = runtime.freeMemory();
        long usedMemory = totalMemory - freeMemory;

        System.out.println(label + ": " + (usedMemory / 1024 / 1024) + " MB");
    }
}

Python Profiling

import tracemalloc
import sys

# Memory tracing
tracemalloc.start()

# Your code here
def memory_intensive_function():
    large_list = [i for i in range(1000000)]
    return sum(large_list)

result = memory_intensive_function()

# Get memory statistics
current, peak = tracemalloc.get_traced_memory()
print(f"Current memory usage: {current / 1024 / 1024:.2f} MB")
print(f"Peak memory usage: {peak / 1024 / 1024:.2f} MB")

# Get top memory consumers
snapshot = tracemalloc.take_snapshot()
top_stats = snapshot.statistics('lineno')
for stat in top_stats[:10]:
    print(stat)

C Memory Debugging

# Using Valgrind
gcc -g program.c -o program
valgrind --tool=memcheck --leak-check=full ./program

# Using AddressSanitizer
gcc -fsanitize=address -g program.c -o program
./program

# Memory leak detection
# In code:
#include <stdlib.h>

void* safe_malloc(size_t size) {
    void* ptr = malloc(size);
    if (ptr == NULL) {
        fprintf(stderr, "Memory allocation failed\n");
        exit(1);
    }
    printf("Allocated %zu bytes at %p\n", size, ptr);
    return ptr;
}

void safe_free(void* ptr) {
    if (ptr != NULL) {
        printf("Freeing memory at %p\n", ptr);
        free(ptr);
    }
}

📈 Memory Optimization Patterns

Lazy Loading

# Bad: Load everything upfront
class BadDataLoader:
    def __init__(self):
        self.all_data = self.load_all_data()  # Loads everything

    def get_user(self, user_id):
        return self.all_data[user_id]

# Good: Load on demand
class GoodDataLoader:
    def __init__(self):
        self.cache = {}

    def get_user(self, user_id):
        if user_id not in self.cache:
            self.cache[user_id] = self.load_user(user_id)  # Load only when needed
        return self.cache[user_id]

Memory-Mapped Files

// For large files, use memory mapping
#include <sys/mman.h>
#include <fcntl.h>
#include <unistd.h>

void* map_file(const char* filename, size_t* size) {
    int fd = open(filename, O_RDONLY);
    if (fd == -1) return NULL;

    struct stat sb;
    if (fstat(fd, &sb) == -1) return NULL;

    *size = sb.st_size;
    void* mapped = mmap(NULL, *size, PROT_READ, MAP_PRIVATE, fd, 0);
    close(fd);

    return mapped;  // File mapped into memory
}

Streaming Processing

# Process large datasets without loading everything
def process_large_dataset(filename):
    with open(filename, 'r') as file:
        for line in file:  # Process one line at a time
            data = parse_line(line)
            if meets_criteria(data):
                yield process_data(data)  # Generator, memory efficient

# Usage
for result in process_large_dataset("large_file.txt"):
    handle_result(result)

🧪 Practice Problems

Easy

1. Space Analysis: What is the space complexity of reversing a string in-place?
2. Memory Usage: How much memory does storing 1 million integers require?
3. Optimization: Convert O(n²) space algorithm to O(n) space.

Medium

1. In-Place Operations: Implement in-place quicksort and analyze its space complexity.
2. Memory Pool: Design a memory pool for frequent object allocation/deallocation.
3. Streaming: Process a large CSV file without loading it entirely into memory.

Hard

1. External Sorting: Design an algorithm to sort data that doesn't fit in memory.
2. Memory Mapping: Implement file processing using memory-mapped I/O.
3. Garbage Collection: Analyze memory usage patterns and optimize for GC efficiency.

📚 Related Resources

• Memory Management in Java - Official Java memory guide
• Python Memory Management - Python memory documentation
• C Memory Management - GNU C memory guide

🔗 Related Guides

• Time Complexity - Runtime analysis
• Algorithm Analysis - Comprehensive analysis techniques
• Optimization Techniques - Performance improvement strategies
• Benchmarking Methods - Measuring actual performance

🔗 Language-Specific Memory

• Java Performance Tips - Java memory optimization
• Python Performance Tips - Python memory optimization
• C Performance Tips - C memory management
• Oracle Performance Tips - Oracle memory optimization