Appendix A: Complexity Cheat Sheet

A comprehensive reference for algorithm complexity analysis and common algorithm time/space complexities.

Big O Notation Hierarchy

From fastest to slowest:

Notation	Name	Example	n=10	n=100	n=1000
O(1)	Constant	Array access, hash lookup	1	1	1
O(log n)	Logarithmic	Binary search	3	7	10
O(n)	Linear	Linear search, array iteration	10	100	1,000
O(n log n)	Linearithmic	Merge sort, quick sort (avg)	30	664	9,966
O(n²)	Quadratic	Bubble sort, nested loops	100	10,000	1,000,000
O(n³)	Cubic	Matrix multiplication	1,000	1,000,000	1,000,000,000
O(2ⁿ)	Exponential	Recursive Fibonacci	1,024	1.27×10³⁰	∞
O(n!)	Factorial	Traveling salesman (brute force)	3,628,800	∞	∞

Practical Limits (1 second execution)

Complexity	Maximum n
O(1)	∞
O(log n)	∞
O(n)	~100,000,000
O(n log n)	~10,000,000
O(n²)	~10,000
O(n³)	~500
O(2ⁿ)	~25
O(n!)	~11

Visual Complexity Growth Chart

Operations performed (y-axis) vs Input Size (x-axis)

n=10          n=100         n=1000        n=10000
│             │             │             │
│             │             │             │         O(n!)
│             │             │             │xxxxxxxxx
│             │             │ xxxxxxxxxxxx│
│             │ xxxxxxxxxxxx│             │
│ xxxxxxxxxxxx│             │             │         O(2^n)
│             │             │             │xxxxxxx
│             │             │ xxxxxxxxxxx│
│             │ xxxxxxxxxxx│             │
│ xxxxxxxxxxx│             │             │         O(n³)
│             │             │             │xxxxx
│             │             │ xxxxxxxxx  │
│             │ xxxxxxxxx  │             │
│ xxxxxxxxx  │             │             │         O(n²)
│             │             │      xxxx  │
│             │      xxx   │             │
│      xx    │             │             │         O(n log n)
│             │       xx   │        xx   │
│        x   │             │             │         O(n)
│         x  │          x  │           x │
│          x │             │             x         O(log n)
│xxxxxxxxxx ─┼─────────x ─┼────────────x┼─        O(1)
└────────────┴─────────────┴─────────────┴─────────

Legend: Lower = Better Performance

Complexity Comparison for n=100

Algorithm     Operations  Visualization
O(1)          1          █
O(log n)      7          ███
O(n)          100        ██████████
O(n log n)    664        ████████████████████████████████████
O(n²)         10,000     ████████████████████████████████████████████████████... (entire screen!)
O(2^n)        1.27×10³⁰  (larger than atoms in universe)

Key Insight: Even small differences in complexity class have MASSIVE impacts as input grows!

Practical PHP Examples by Complexity

O(1) - Constant Time:

<?php
declare(strict_types=1);

// Direct array access
$value = $array[$key];  // Always same time

// Hash table operations
isset($cache[$key]);    // Instant lookup
unset($map[$key]);      // Instant delete

See: Chapter 4 (Arrays), Chapter 6 (Hash Tables)

O(log n) - Logarithmic:

<?php
declare(strict_types=1);

// Binary search on sorted array
$index = binarySearch($sortedArray, $target);

// Operations on balanced BST
$tree->search($value);  // Height = log n

See: Chapter 8 (Binary Search), Chapter 16 (Binary Search Trees)

O(n) - Linear:

<?php
declare(strict_types=1);

// Single loop through array
foreach ($array as $item) {
    process($item);
}

// Linear search
$found = in_array($needle, $haystack);

See: Chapter 4 (Array Traversal), Chapter 7 (Linear Search)

O(n log n) - Linearithmic:

<?php
declare(strict_types=1);

// Efficient sorting
sort($array);           // PHP's built-in
$merged = mergeSort($array);  // Merge sort

See: Chapter 10-11 (Sorting Algorithms)

O(n²) - Quadratic:

<?php
declare(strict_types=1);

// Nested loops
$count = count($arr);
for ($i = 0; $i < $count; $i++) {
    for ($j = $i + 1; $j < $count; $j++) {
        comparePair($arr[$i], $arr[$j]);
    }
}

See: Chapter 9 (Bubble Sort), Chapter 11 (Selection Sort)

O(2^n) - Exponential:

<?php
declare(strict_types=1);

// Naive recursive Fibonacci
function fib(int $n): int {
    if ($n <= 1) return $n;
    return fib($n-1) + fib($n-2);  // Two recursive calls
}

See: Chapter 25 (Dynamic Programming - shows optimization)

O(n!) - Factorial:

<?php
declare(strict_types=1);

// Generate all permutations
function permutations(array $items): array {
    if (count($items) <= 1) return [$items];

    $result = [];
    foreach ($items as $i => $item) {
        $rest = $items;
        unset($rest[$i]);
        foreach (permutations(array_values($rest)) as $perm) {
            $result[] = array_merge([$item], $perm);
        }
    }
    return $result;
}

See: Chapter 25 (Dynamic Programming - shows optimization)

Common Data Structure Operations

Array (PHP array with numeric keys)

Operation	Average	Worst	Notes
Access by index	O(1)	O(1)	Direct access
Search (unsorted)	O(n)	O(n)	Linear scan
Search (sorted)	O(log n)	O(log n)	Binary search
Insert at end	O(1)	O(1)	`$arr[] = $value`
Insert at beginning	O(n)	O(n)	`array_unshift()`
Insert at middle	O(n)	O(n)	Shift elements
Delete at end	O(1)	O(1)	`array_pop()`
Delete at beginning	O(n)	O(n)	`array_shift()`
Delete at middle	O(n)	O(n)	Shift elements

Hash Table (PHP associative array)

Operation	Average	Worst	Notes
Access	O(1)	O(n)	Key lookup
Search	O(1)	O(n)	`isset()`, `array_key_exists()`
Insert	O(1)	O(n)	`$arr[$key] = $value`
Delete	O(1)	O(n)	`unset($arr[$key])`
Iteration	O(n)	O(n)	`foreach`

Stack (using SplStack or array)

Operation	Time	Notes
Push	O(1)	`$stack->push()` or `array_push()`
Pop	O(1)	`$stack->pop()` or `array_pop()`
Peek	O(1)	`$stack->top()` or `end()`
Search	O(n)	Linear scan

Queue (using SplQueue or array)

Operation	Time	Notes
Enqueue	O(1)	`$queue->enqueue()`
Dequeue	O(1)	`$queue->dequeue()`
Peek	O(1)	Front element
Search	O(n)	Linear scan

Binary Search Tree (Balanced)

Operation	Average	Worst (unbalanced)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)
Min/Max	O(log n)	O(n)

AVL Tree

Operation	Time	Space	Notes
Search	O(log n)	O(1)	Height bounded by 1.44 × log(n)
Insert	O(log n)	O(1)	May require rotations
Delete	O(log n)	O(1)	May require rotations
Min/Max	O(log n)	O(1)	Height field per node
Space	O(n)	O(n)	Strict balance maintained

Red-Black Tree

Operation	Time	Space	Notes
Search	O(log n)	O(1)	Height bounded by 2 × log(n)
Insert	O(log n)	O(1)	Max 2 rotations
Delete	O(log n)	O(1)	Max 3 rotations
Min/Max	O(log n)	O(1)	Color bit per node
Space	O(n)	O(n)	Looser balance than AVL

Comparison:

AVL: Stricter balance, faster searches, more rotations on insert/delete
Red-Black: Looser balance, faster insertions/deletions, slightly slower searches
Both guarantee O(log n) worst-case performance

See: Chapter 20 (Balanced Trees: AVL & Red-Black Trees)

Heap (SplPriorityQueue, SplMinHeap, SplMaxHeap)

Operation	Time
Insert	O(log n)
Extract min/max	O(log n)
Peek min/max	O(1)
Build heap	O(n)
Heapify	O(log n)

Graph (Adjacency List)

Operation	Time	Space
Add vertex	O(1)	O(1)
Add edge	O(1)	O(1)
Remove vertex	O(V + E)	-
Remove edge	O(E)	-
Query edge	O(V)	-

Sorting Algorithms

Algorithm	Best	Average	Worst	Space	Stable	Notes
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Simple, slow
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No	Always O(n²)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Good for small/nearly sorted
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	Predictable, needs space
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Fast average, in-place
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	In-place, not stable
Counting Sort	O(n + k)	O(n + k)	O(n + k)	O(k)	Yes	Integer keys only
Radix Sort	O(nk)	O(nk)	O(nk)	O(n + k)	Yes	Integer keys
Bucket Sort	O(n + k)	O(n + k)	O(n²)	O(n)	Yes	Uniform distribution

PHP’s sort() and usort(): O(n log n) average (uses quicksort variant)

Searching Algorithms

Algorithm	Time	Space	Notes
Linear Search	O(n)	O(1)	Unsorted data
Binary Search	O(log n)	O(1)	Sorted data required
Jump Search	O(√n)	O(1)	Sorted data
Interpolation Search	O(log log n) avg	O(1)	Uniformly distributed
Hash Table Lookup	O(1) avg	O(n)	PHP arrays
Binary Search Tree	O(log n) avg	O(n)	Balanced tree
Depth-First Search (DFS)	O(V + E)	O(V)	Graph traversal
Breadth-First Search (BFS)	O(V + E)	O(V)	Graph traversal

Graph Algorithms

Algorithm	Time Complexity	Space	Use Case
DFS	O(V + E)	O(V)	Traversal, cycles
BFS	O(V + E)	O(V)	Shortest path (unweighted)
Dijkstra	O((V + E) log V)	O(V)	Shortest path (weighted)
Bellman-Ford	O(VE)	O(V)	Negative weights allowed
Floyd-Warshall	O(V³)	O(V²)	All-pairs shortest paths
Prim’s	O((V + E) log V)	O(V)	Minimum spanning tree
Kruskal’s	O(E log E)	O(V)	Minimum spanning tree
Topological Sort	O(V + E)	O(V)	DAG ordering

String Algorithms

Algorithm	Time	Space	Use Case
Naive String Match	O(nm)	O(1)	Simple pattern search
KMP	O(n + m)	O(m)	Pattern matching
Boyer-Moore	O(n/m) best	O(m)	Fast pattern matching
Rabin-Karp	O(n + m) avg, O(nm) worst	O(1)	Multiple patterns
Aho-Corasick	O(n + m + z)	O(m × σ)	Multi-pattern search
Z-Algorithm	O(n + m)	O(n + m)	Fast pattern matching
Suffix Array	O(n log n) build, O(m log n + occ) search	O(n)	Substring queries
Suffix Tree	O(n) build (Ukkonen’s), O(m) search	O(n)	Linear-time pattern matching
Longest Common Subsequence	O(nm)	O(nm)	Sequence comparison
Edit Distance	O(nm)	O(nm)	String similarity
Manacher’s Algorithm	O(n)	O(n)	Palindrome finding

Notes:

Aho-Corasick: n = text length, m = total pattern length, z = number of matches, σ = alphabet size
Suffix Array: occ = number of occurrences, specialized algorithms can build in O(n)
Suffix Tree: Uses Ukkonen’s algorithm for linear construction

Dynamic Programming Problems

Problem	Time	Space
Fibonacci (naive)	O(2ⁿ)	O(n)
Fibonacci (DP)	O(n)	O(n)
Fibonacci (optimized)	O(n)	O(1)
0/1 Knapsack	O(nW)	O(nW)
Longest Common Subsequence	O(nm)	O(nm)
Longest Increasing Subsequence	O(n²) or O(n log n)	O(n)
Matrix Chain Multiplication	O(n³)	O(n²)
Edit Distance	O(nm)	O(nm)
Coin Change	O(nA)	O(n)

Stream Processing Algorithms

Stream processing algorithms handle continuous, potentially infinite data streams with constant or logarithmic space complexity.

Algorithm	Time per Element	Space	Notes
Fixed-Size Sliding Window	O(1) add/sum/avg, O(n) min/max	O(n)	Window size n
Optimized Sliding Window	O(1) amortized all ops	O(n)	Uses monotonic queues
Time-Based Sliding Window	O(1) add, O(n) cleanup	O(n)	n = events in window
Token Bucket Rate Limiter	O(1)	O(1)	Constant space
Leaky Bucket Rate Limiter	O(1)	O(1)	Constant space
Sliding Window Counter	O(1)	O(k)	k = time buckets
Moving Average (SMA)	O(1)	O(n)	n = window size
Exponential Moving Average (EMA)	O(1)	O(1)	Constant space
Top-K Elements	O(1) add, O(n log n) query	O(n)	n = unique elements
Reservoir Sampling	O(1)	O(k)	k = sample size
Stream Aggregator	O(1) per record	O(n)	n = stored values

See: Chapter 36 (Stream Processing Algorithms)

Probabilistic Algorithms

Probabilistic algorithms trade perfect accuracy for dramatic space/time improvements, essential for big data processing.

Algorithm	Time	Space	Accuracy	Use Case
Bloom Filter	O(k) add/contains	O(m)	No false negatives	Membership testing
HyperLogLog	O(1) add	O(2^p)	±0.81% (p=14)	Cardinality estimation
Count-Min Sketch	O(d) add/estimate	O(w×d)	±εN	Frequency estimation
Reservoir Sampling	O(1) add	O(k)	Exact distribution	Random sampling
Morris Counter	O(1) increment	O(1)	±√n	Approximate counting
Skip List	O(log n) avg	O(n log n)	Exact	Sorted set operations

Notes:

Bloom Filter: k = number of hash functions, m = bit array size
HyperLogLog: p = precision parameter (typically 14)
Count-Min Sketch: w = width, d = depth (hash functions)
Reservoir Sampling: k = sample size

See: Chapter 32 (Probabilistic Algorithms)

Concurrent Algorithms

Concurrent algorithms enable parallel execution, dramatically improving performance for I/O-bound and CPU-intensive tasks.

Pattern	Time Complexity	Space	Notes
Async I/O (ReactPHP)	O(1) scheduling	O(n)	n = concurrent operations
Parallel Processing	O(n/p)	O(n)	p = processors
Coroutines (Swoole)	O(1) yield/resume	O(k)	k = coroutine stack
Worker Pool	O(n/p)	O(p)	p = workers, n = tasks
Pipeline Processing	O(n)	O(k)	k = pipeline stages
Fork-Join	O(n/p + log p)	O(n)	Divide and conquer

Notes:

Concurrent algorithms reduce wall-clock time but may increase total CPU time
Space complexity often increases due to multiple execution contexts
Actual speedup depends on I/O wait time and CPU cores available

See: Chapter 31 (Concurrent Algorithms)

Common PHP Function Complexities

Array Functions

Function	Time	Space	Notes
`in_array()`	O(n)	O(1)	Linear search - avoid in loops
`array_search()`	O(n)	O(1)	Linear search - returns key
`isset()`	O(1)	O(1)	Hash lookup - use for membership
`array_key_exists()`	O(1)	O(1)	Hash lookup - checks null values too
`count()`	O(1)	O(1)	Stored value - cache outside loops
`array_push()`	O(1)	O(1)	Append - same as `$arr[] = $val`
`array_pop()`	O(1)	O(1)	Remove last
`array_shift()`	O(n)	O(1)	Remove first, reindex - use SplQueue
`array_unshift()`	O(n)	O(1)	Prepend, reindex - expensive
`array_merge()`	O(n + m)	O(n + m)	Combine arrays
`array_merge_recursive()`	O(n + m)	O(n + m)	Deep merge
`array_combine()`	O(n)	O(n)	Keys + values to array
`array_fill()`	O(n)	O(n)	Fill with value
`array_pad()`	O(n)	O(n)	Pad to length
`array_chunk()`	O(n)	O(n)	Split into chunks
`array_column()`	O(n)	O(n)	Extract column from 2D array
`array_flip()`	O(n)	O(n)	Swap keys and values
`array_intersect()`	O(n * m)	O(n)	Common values
`array_diff()`	O(n * m)	O(n)	Difference
`array_values()`	O(n)	O(n)	Reindex numerically
`array_keys()`	O(n)	O(n)	Extract keys
`sort()`	O(n log n)	O(log n)	Quicksort variant
`rsort()`	O(n log n)	O(log n)	Reverse sort
`asort()`	O(n log n)	O(log n)	Sort maintaining keys
`ksort()`	O(n log n)	O(log n)	Sort by keys
`usort()`	O(n log n)	O(log n)	Custom comparison sort
`array_unique()`	O(n)	O(n)	Hash-based deduplication
`array_filter()`	O(n)	O(n)	Iterate + callback
`array_map()`	O(n)	O(n)	Iterate + transform
`array_reduce()`	O(n)	O(1)	Iterate + accumulate
`array_walk()`	O(n)	O(1)	In-place modification
`array_reverse()`	O(n)	O(n)	Reverse order
`array_slice()`	O(k)	O(k)	Extract k elements
`array_splice()`	O(n)	O(k)	Remove and replace
`array_sum()`	O(n)	O(1)	Sum numeric array
`array_product()`	O(n)	O(1)	Product of array
`min()` / `max()`	O(n)	O(1)	Find min/max in array

String Functions

Function	Time	Space	Notes
`strlen()`	O(1)	O(1)	Cached length
`substr()`	O(k)	O(k)	Extract k characters
`strpos()`	O(n)	O(1)	Find substring - fast
`str_contains()`	O(n)	O(1)	PHP 8.0+ - check substring
`str_starts_with()`	O(m)	O(1)	PHP 8.0+ - check prefix
`str_ends_with()`	O(m)	O(1)	PHP 8.0+ - check suffix
`str_replace()`	O(n)	O(n)	Simple replacement
`str_ireplace()`	O(n)	O(n)	Case-insensitive replace
`preg_match()`	O(n) avg	O(1)	Regex - can be O(2^n) worst
`preg_replace()`	O(n) avg	O(n)	Regex replacement
`explode()`	O(n)	O(n)	Split string
`implode()`	O(n)	O(n)	Join strings
`trim()` / `ltrim()` / `rtrim()`	O(n)	O(n)	Remove whitespace
`strtoupper()` / `strtolower()`	O(n)	O(n)	Case conversion
`strcmp()`	O(n)	O(1)	String comparison
`levenshtein()`	O(n * m)	O(n * m)	Edit distance

PHP 8.0+ Modern Functions

Function	Time	Space	Notes
`str_contains()`	O(n)	O(1)	Better than `strpos() !== false`
`str_starts_with()`	O(m)	O(1)	Better than `substr($str, 0, m)`
`str_ends_with()`	O(m)	O(1)	Better than substring comparison
`array_is_list()`	O(n)	O(1)	Check if sequential numeric keys
`fdiv()`	O(1)	O(1)	Division by zero returns INF
Match expression	O(1)	O(1)	Strict comparison switch

PHP 8.4+ Features

Feature	Time	Space	Notes
Property hooks	O(1)	O(1)	Overhead per property access
Asymmetric visibility	O(1)	O(1)	No performance impact
Typed class constants	O(1)	O(1)	Compile-time check
Override attribute	O(1)	O(1)	Compile-time validation

SPL Data Structure Operations

Operation	SplStack	SplQueue	SplHeap	SplFixedArray
Access	O(1) top	O(1) front	O(1) top	O(1) by index
Insert	O(1) push	O(1) enqueue	O(log n)	O(1) at index
Delete	O(1) pop	O(1) dequeue	O(log n)	O(1) at index
Search	O(n)	O(n)	O(n)	O(n)
Space	O(n)	O(n)	O(n)	O(n) fixed

Example: When to use each:

<?php
declare(strict_types=1);

// ❌ BAD: Using array_shift in loop (O(n²) total)
while (count($arr) > 0) {
    $item = array_shift($arr);  // O(n) each time
    process($item);
}

// ✅ GOOD: Using SplQueue (O(n) total)
$queue = new SplQueue();
foreach ($arr as $item) {
    $queue->enqueue($item);
}
while (!$queue->isEmpty()) {
    $item = $queue->dequeue();  // O(1) each time
    process($item);
}

Space Complexity Guide

Common Patterns

Pattern	Space	Example
In-place algorithm	O(1)	Bubble sort, two pointers
Single array/variable	O(n)	Hash table, visited set
Two arrays	O(n)	Merge sort temp array
Matrix	O(n²)	Floyd-Warshall, DP table
Recursion depth	O(n)	DFS call stack
Complete binary tree	O(2ⁿ)	All subsets generation
Stream processing	O(1) or O(log n)	Sliding windows, aggregations
Probabilistic structures	O(1) to O(k)	Bloom filters, sketches
Concurrent contexts	O(p)	p = parallel workers/threads

PHP-Specific Memory Considerations

<?php
declare(strict_types=1);

// Array overhead
$arr = [];  // ~56 bytes base
$arr[] = 1; // ~72 bytes per element (with overhead)

// String memory
$str = '';  // ~24 bytes base
$str = 'hello';  // 24 + 5 bytes

// Object overhead
class Foo {}
$obj = new Foo();  // ~40 bytes minimum

Algorithm Selection Guide

Sorting

Small dataset (n < 100):

Insertion Sort O(n²) - Simple, efficient for small data

Medium dataset (100 < n < 1M):

Quick Sort O(n log n) - Fast average case
PHP’s sort() - Optimized built-in

Large dataset (n > 1M):

Merge Sort O(n log n) - Predictable performance
Timsort (Python, Java) - Hybrid approach

Special cases:

Nearly sorted: Insertion Sort O(n)
Integer keys, small range: Counting Sort O(n + k)
Need stability: Merge Sort
Memory constrained: Heap Sort

Searching

Unsorted data:

Linear Search O(n) - Only option

Sorted data:

Binary Search O(log n) - Optimal

Frequent lookups:

Hash Table O(1) - Best average case
PHP associative array

Range queries:

Binary Search Tree O(log n)
Segment Tree O(log n)

Graph Traversal

Shortest path (unweighted):

BFS O(V + E)

Shortest path (weighted, non-negative):

Dijkstra O((V + E) log V)

Shortest path (negative weights):

Bellman-Ford O(VE)

All-pairs shortest path:

Floyd-Warshall O(V³)

Minimum spanning tree:

Prim’s O((V + E) log V) - Dense graphs
Kruskal’s O(E log E) - Sparse graphs

Optimization Techniques

Time Optimization

Use appropriate data structure
- Hash table for O(1) lookup
- Heap for O(log n) min/max
Avoid nested loops
- O(n²) → O(n) using hash table
Use binary search
- O(n) → O(log n) for sorted data
Memoization
- O(2ⁿ) → O(n) for recursive problems
Early termination
- Break loops when answer found

Space Optimization

In-place algorithms
- Modify input instead of creating new array
Two pointers
- O(n) space → O(1) space
Iterative vs recursive
- O(n) stack space → O(1) space
Sliding window
- O(n) → O(k) where k is window size
Rolling hash
- O(m) → O(1) for pattern matching

Quick Reference: When to Use What

Need O(1) lookup?

→ Hash table (PHP array)

Need sorted data?

→ Binary Search Tree or sorted array

Need min/max quickly?

→ Heap (SplPriorityQueue)

Need FIFO?

→ Queue (SplQueue)

Need LIFO?

→ Stack (SplStack)

Need to find duplicates?

→ Hash table O(n)

Need to reverse?

→ Two pointers O(n), O(1) space

Need substring search?

→ KMP O(n + m) or PHP strpos() O(n)

Need shortest path?

→ BFS (unweighted) or Dijkstra (weighted)

Need to sort?

→ PHP sort() O(n log n)

Need rate limiting?

→ Token Bucket O(1) time, O(1) space → Sliding Window Counter O(1) time, O(k) space

Need to track unique items in stream?

→ HyperLogLog O(1) add, O(2^p) space → Bloom Filter O(k) add/check, O(m) space

Need frequency counts in stream?

→ Count-Min Sketch O(d) add/estimate, O(w×d) space

Need parallel processing?

→ Worker Pool O(n/p) time, O(p) space → Async I/O O(1) scheduling, O(n) space

Common Mistakes to Avoid

❌ Using in_array() in loop → O(n²) ✅ Use hash table → O(n)
❌ Multiple array_shift() → O(n²) ✅ Use SplQueue → O(n)
❌ String concatenation in loop → O(n²) ✅ Use array + implode() → O(n)
❌ Nested foreach without thinking → O(n²) ✅ Consider hash table approach → O(n)
❌ Sorting already sorted data repeatedly ✅ Check if sorted first or maintain sorted order
❌ Using array_shift() in sliding window → O(n²) total ✅ Use deque or circular buffer → O(1) per operation
❌ Storing entire stream in memory → O(n) space ✅ Use stream processing algorithms → O(1) or O(log n) space
❌ Exact counting for billions of items → O(n) space ✅ Use probabilistic algorithms (Bloom filter, HyperLogLog) → O(1) or O(log n) space

Performance Testing Template

<?php
declare(strict_types=1);

function measureTime(callable $fn, mixed ...$args): float {
    $start = microtime(true);
    $fn(...$args);
    return microtime(true) - $start;
}

function measureMemory(callable $fn, mixed ...$args): int {
    $before = memory_get_usage();
    $fn(...$args);
    return memory_get_usage() - $before;
}

// Usage
$time = measureTime(fn() => myAlgorithm($data));
$memory = measureMemory(fn() => myAlgorithm($data));

echo "Time: " . number_format($time * 1000, 2) . " ms\n";
echo "Memory: " . number_format($memory / 1024, 2) . " KB\n";

Real-World Optimization Decisions

When to Optimize?

Don’t optimize if:

Data size is small (n < 100)
Code runs rarely (batch jobs, migrations)
Code is clearer without optimization
Time saved is negligible

Do optimize if:

Data size is large (n > 10,000)
Code runs frequently (API endpoints, real-time systems)
User experience is affected (page load time)
Resource costs are high (server costs, memory)

Optimization Priority Matrix

Impact vs Effort

High Impact, Low Effort  ← START HERE
  ├─ Replace in_array() with isset()
  ├─ Cache count() outside loops
  ├─ Use native sort() instead of custom O(n²)
  └─ Enable OPcache

High Impact, High Effort  ← DO AFTER QUICK WINS
  ├─ Implement caching layer (Redis/Memcached)
  ├─ Database query optimization
  ├─ Algorithm redesign (e.g., O(n²) → O(n))
  └─ Data structure refactoring

Low Impact, Low Effort  ← DO IF TIME PERMITS
  ├─ Code style improvements
  ├─ Minor refactoring
  └─ Comment additions

Low Impact, High Effort  ← AVOID
  ├─ Micro-optimizations
  ├─ Premature optimization
  └─ Over-engineering

Real Production Examples

Example 1: E-commerce Product Search

<?php
declare(strict_types=1);

// ❌ BAD: O(n²) - checking duplicates in loop
$filtered = [];
foreach ($products as $product) {
    if (!in_array($product->id, $filtered)) {  // O(n) each time
        $filtered[] = $product->id;
    }
}
// With 10,000 products: 10,000² = 100M operations!

// ✅ GOOD: O(n) - using hash table
$seen = [];
$filtered = [];
foreach ($products as $product) {
    if (!isset($seen[$product->id])) {  // O(1) each time
        $filtered[] = $product->id;
        $seen[$product->id] = true;
    }
}
// With 10,000 products: 10,000 operations (10,000x faster!)

Impact: Page load reduced from 5s to 50ms

Example 2: User Activity Feed

<?php
declare(strict_types=1);

// ❌ BAD: N+1 query problem
$posts = $db->query("SELECT * FROM posts LIMIT 50");
foreach ($posts as $post) {
    $user = $db->query("SELECT * FROM users WHERE id = {$post['user_id']}");
    $post['author'] = $user;
}
// 51 database queries!

// ✅ GOOD: Single JOIN query
$posts = $db->query("
    SELECT posts.*, users.name, users.avatar
    FROM posts
    JOIN users ON posts.user_id = users.id
    LIMIT 50
");
// 1 database query (51x fewer queries!)

Impact: API response time reduced from 800ms to 15ms

Example 3: Log Processing

<?php
declare(strict_types=1);

// ❌ BAD: String concatenation in loop
$log = '';
foreach ($entries as $entry) {
    $log .= $entry . "\n";  // Creates new string each time
}
// O(n²) time, O(n²) memory with 100,000 entries = 10B operations!

// ✅ GOOD: Array + implode
$lines = [];
foreach ($entries as $entry) {
    $lines[] = $entry;
}
$log = implode("\n", $lines);
// O(n) time, O(n) memory with 100,000 entries = 100K operations

Impact: Memory usage reduced from 5GB to 50MB

Cross-Reference Guide

By Chapter

Fundamentals:

Chapter 1: Introduction to Algorithms → Big O basics
Chapter 2: Time Complexity Analysis → Detailed complexity analysis
Chapter 3: Space Complexity → Memory usage patterns

Data Structures:

Chapter 4: Arrays and Lists → Array operations (this appendix)
Chapter 5: Stacks and Queues → Stack/Queue complexity
Chapter 6: Hash Tables → O(1) lookup patterns
Chapter 14: Heaps → Heap operations and Priority Queues
Chapter 16: Binary Search Trees → Tree operations
Chapter 17: Balanced Trees → AVL/Red-Black tree guarantees
Chapter 18: Tree Traversals → DFS/BFS complexity
Chapter 20: Balanced Trees (AVL & Red-Black) → Self-balancing tree operations

Algorithms:

Chapter 7: Linear Search → O(n) search
Chapter 8: Binary Search → O(log n) search
Chapter 9-13: Sorting Algorithms → Sorting comparison table
Chapter 19: Graph Representations → Graph storage complexity
Chapter 20-22: Graph Algorithms → DFS, BFS, Dijkstra complexity
Chapter 23: String Algorithms → Pattern matching complexity
Chapter 33: String Algorithms Deep Dive → Advanced string algorithms (Z-algorithm, Suffix Tree)
Chapter 25: Dynamic Programming → Memoization patterns
Chapter 31: Concurrent Algorithms → Parallel processing patterns
Chapter 32: Probabilistic Algorithms → Space-efficient data structures
Chapter 36: Stream Processing → Real-time algorithms

Optimization:

Chapter 29: Performance Optimization → Practical optimization
Appendix B: PHP Performance Tips → PHP-specific optimizations

By Problem Type

Need O(1) lookup? → Chapter 6: Hash Tables → This appendix: Hash Table section

Need to sort efficiently? → Chapter 10: Merge Sort → Chapter 12: Quick Sort → This appendix: Sorting Algorithms table

Need shortest path? → Chapter 20: BFS (unweighted) → Chapter 22: Dijkstra (weighted) → This appendix: Graph Algorithms table

Need to optimize recursive algorithm? → Chapter 25: Dynamic Programming → This appendix: DP Problems table

Working with strings? → Chapter 23: String Algorithms → Chapter 33: String Algorithms Deep Dive (advanced) → This appendix: String Algorithms table

Processing data streams? → Chapter 36: Stream Processing Algorithms → This appendix: Stream Processing Algorithms table

Need space-efficient solutions? → Chapter 32: Probabilistic Algorithms → This appendix: Probabilistic Algorithms table

Need parallel processing? → Chapter 31: Concurrent Algorithms → This appendix: Concurrent Algorithms table

Quick Decision Tree

Start: I need to process data
│
├─ Known operation on standard data?
│  └─ Use this appendix to find complexity
│
├─ Custom algorithm needed?
│  ├─ Search problem?
│  │  ├─ Sorted? → Chapter 8: Binary Search
│  │  └─ Unsorted? → Chapter 7: Linear Search
│  │
│  ├─ Sorting problem?
│  │  └─ Chapter 9-13: Sorting Algorithms
│  │
│  ├─ Graph problem?
│  │  └─ Chapter 19-22: Graph Algorithms
│  │
│  ├─ Optimization problem?
│  │  └─ Chapter 25: Dynamic Programming
│  │
│  ├─ Stream processing?
│  │  └─ Chapter 36: Stream Processing Algorithms
│  │
│  ├─ Big data / space constraints?
│  │  └─ Chapter 32: Probabilistic Algorithms
│  │
│  └─ Need parallel/concurrent?
│     └─ Chapter 31: Concurrent Algorithms
│
└─ Performance issue?
   ├─ Algorithm complexity? → This appendix
   ├─ PHP-specific? → Appendix B
   └─ Profiling needed? → Chapter 29

Resources

External References

Big-O Cheat Sheet - Interactive complexity visualization
PHP Manual: Data Structures - Official SPL documentation
PHP Manual: Array Functions - Complete function reference

This Series

Chapter 1: Introduction to Algorithms
Chapter 2: Time Complexity Analysis - Deep dive into Big O
Chapter 3: Space Complexity - Memory usage analysis
Chapter 4: Arrays and Lists - Array operations
Chapter 6: Hash Tables - O(1) data structures
Chapter 8: Binary Search - O(log n) searching
Chapter 10-13: Sorting Algorithms - Complete sorting guide
Chapter 25: Dynamic Programming - Optimization techniques
Chapter 29: Performance Optimization - Real-world optimization
Chapter 31: Concurrent Algorithms - Parallel processing patterns
Chapter 30: Real-World Case Studies - Practical algorithm applications
Chapter 32: Probabilistic Algorithms - Space-efficient data structures
Chapter 33: String Algorithms Deep Dive - Advanced string matching
Chapter 36: Stream Processing Algorithms - Real-time data processing
Appendix B: PHP Performance Tips - PHP-specific optimizations
Appendix C: Glossary - Algorithm terminology