Performance Analysis

Time Complexity

Naive: O(n * k)
Each of n positions processes window of size k

Sliding: O(n)
Process n positions, each takes O(1)

Speedup: n*k / n = k (k times faster!)

Space Complexity

Window data: O(k)
Helper structures: O(k) for deque/hash

Total: O(k)

Not dependent on input size!

Real Numbers

Array: 1,000,000 elements
Window: 1,000

Naive: 1,000,000 * 1,000 = 1B operations → 1 second
Sliding: 1,000,000 operations → 1ms

1000x faster!

Bottlenecks

Window operation: Check each element
Solution: Deque (O(1) per add/remove)

Calculating metric: Recalculate each window
Solution: Incremental updates

Finding min/max: Search window
Solution: Monotonic deque or heap

Optimization Checklist

□ Sliding window reduces outer loop
□ Incremental updates avoid recalculation
□ Correct data structure chosen
□ No unnecessary memory allocations
□ Early termination if possible

Benchmarking

import time

# Naive approach
start = time.time()
result_naive = naive_max_subarray(arr, k)
time_naive = time.time() - start

# Sliding window
start = time.time()
result_sliding = sliding_max_subarray(arr, k)
time_sliding = time.time() - start

speedup = time_naive / time_sliding