Blog
Mert Özen's blog posts on software development, backend, frontend, and DevOps.
What Big-O Doesn't Tell You: Constants, Cache and Measuring with BenchmarkDotNet
Big-O tells you about growth, but real time is decided by constants, the cache, allocations and the input distribution. An O(n²) insertion sort twice as fast as LINQ on 10 books, LinkedList 3.8x slower, Dictionary falling to O(n²) with a bad GetHashCode, and estimating complexity by measuring with the doubling experiment.
Amortized Analysis: Why List<T>.Add Counts as O(1)
List<T>.Add sometimes copies the whole list, but because capacity doubles, the total cost of n Adds never exceeds 3n; that's why it counts as amortized O(1). The aggregate, accounting and potential methods, 50 billion copies with +10 growth, Dictionary's prime sizes and a 38 ms resize spike, with real measurements.
Space Complexity: Auxiliary Memory, Recursion Stack and Allocations
Space complexity is how the memory an algorithm keeps alive at once grows with n; recursion depth is memory on the stack too. Recursion failing on a 1.5 MB thread stack, Split vs Span, memoization and reading a 1 GB log file in 52 MB; what ReadAllLines does in a 512 MB container, with real output.
Deriving Time Complexity from Code: Loops, log n and Recursion
To read complexity from code, add sequential blocks, multiply nested loops, call a loop that halves every step log n, and write a recurrence for recursion. With real counts: triangular loops, naive Fibonacci, merge sort, the master theorem, LINQ's hidden loops and an order-matching benchmark going from O(n·m) to O(n+m).
What Is Big-O Notation: Growth Rate, O, Ω, Θ and Worst Case
Big-O describes an algorithm's cost not in seconds but by how its step count grows as the input size n grows. The difference between O, Ω and Θ, choosing n correctly, best/average/worst case, and the real growth of List, HashSet and binary search from 10 to 1,000,000 elements measured with BenchmarkDotNet.