Why Your O(log n) Algorithm Might Lose to O(n)

Code Confessions is a platform or blog where developers share their experiences, challenges, and insights from their journey in software development. Through personal anecdotes, lessons learned, and reflections on coding practices, Code Confessions offers a candid and relatable perspective on the joys and struggles of being a programmer. Readers can find inspiration, empathy, and  lessons from the stories shared by fellow developers.

Confessions of a Code Addict

Explores why algorithms with better time complexity don't always perform better in practice. Compares three GCD algorithms (subtraction-based O(n), modulo-based O(log n), and Stein's binary O(log n)) through benchmarks, showing how hardware characteristics like instruction latency, throughput, and IPC can make a theoretically slower algorithm outperform a faster one. Demonstrates that real-world performance depends on both algorithmic efficiency and hardware-friendly implementation choices.

Big O vs Hardware: Better Complexity ≠ Better Performance

Euclid’s Subtraction-based Algorithm for Computing GCD

The Modulo-based Euclidean Algorithm for GCD

Cost of Integer Add vs Integer Division in Hardware

Benchmark #3: Comparing All Three Algorithms