computer-science-theory

Computer Science Theory

Overview

This skill provides the theoretical CS foundations needed for rigorous research: complexity analysis, data structure selection, benchmarking methodology, and system design principles. Use it to make principled algorithmic choices and ensure benchmarks are scientifically valid.

When to Use This Skill

• Analyzing or comparing algorithm complexity
• Choosing the right data structure for a performance-critical path
• Designing a benchmarking study with statistical rigor
• Reasoning about distributed ML training or data pipelines
• Validating algorithm correctness with invariants and property-based tests

---

1. Algorithm Complexity

Big-O Quick Reference

Complexity	Example	Max n for 1s (rough)
O(1)	Hash table lookup	Any
O(log n)	Binary search	Any
O(n)	Linear scan	~10⁸
O(n log n)	Merge sort, FFT	~10⁷
O(n²)	Nested loops, naive DP	~10⁴
O(n³)	Matrix multiplication (naive)	~10³
O(2ⁿ)	Exponential, backtracking	~25

import time, math, numpy as np

def measure_complexity(func, sizes, repeats=5):
    """Empirically measure complexity by timing at different input sizes."""
    times = {}
    for n in sizes:
        data = list(range(n))
        elapsed = []
        for _ in range(repeats):
            start = time.perf_counter()
            func(data)
            elapsed.append(time.perf_counter() - start)
        times[n] = np.median(elapsed)

    # Log-log plot slope estimates complexity class
    log_n = np.log(list(times.keys()))
    log_t = np.log(list(times.values()))
    slope = np.polyfit(log_n, log_t, 1)[0]
    print(f"Empirical complexity slope: {slope:.2f}  (1.0=linear, 2.0=quadratic)")
    return times

# Example: verify that your sort is O(n log n)
def my_sort(data): return sorted(data)
times = measure_complexity(my_sort, [100, 1000, 10000, 100000])

Amortized Analysis

Some operations appear O(n) in worst case but O(1) amortized:

• Dynamic array append: occasional resize is O(n), but amortized O(1)
• Union-Find with path compression: nearly O(1) per operation
• Don't judge a data structure by its worst-case single operation — think about sequences