The comforting lie of constant time complexity

Description

This image presents a philosophical and technical critique of O(1) time complexity, displayed as white text on a stark black background. The title reads, "1. O(1) as an Ideal, Not a Reality." The text argues that the concept of O(1), or constant time, assumes instantaneous access, which is not true in real-world computing. It lists several contingencies that affect performance, including cache locality, data structure alignment, and even physical factors like hardware architecture, cosmic timing, heat, and electrons. The post concludes, "In truth, every O(1) is not access without cost, but access with hidden effort. A lie we tell ourselves for the sake of abstraction." A final quote emphasizes the point: "O(1) is the myth of certainty in a world that is uncertain by design." This resonates deeply with senior engineers who have moved past purely theoretical algorithm analysis and have had to debug real-world performance issues where factors like CPU cache misses and memory layout have tangible impacts. It's a commentary on the necessary but imperfect abstractions we use in software engineering

Common Tags

BigONotation AlgorithmComplexityAnalysis PerformanceTradeoffs CPUCache CacheInvalidation DataStructures LowLevelProgramming

Comments

Anonymous ★ Top Pick We tell juniors that hash map access is O(1). We tell seniors it's O(1) until the 17th collision, the cache line evicts, and a cosmic ray flips a bit in the memory controller

Anonymous ★ Top Pick

We tell juniors that hash map access is O(1). We tell seniors it's O(1) until the 17th collision, the cache line evicts, and a cosmic ray flips a bit in the memory controller
Anonymous

Every time someone writes “// O(1) lookup” in a PR, a cache line misses, the TLB sighs, and the NUMA gods add 200 ns of latency - constancy preserved exclusively in the comment
Anonymous

After 20 years of optimizing systems, I've learned that O(1) is like 'unlimited PTO' - technically true, but try explaining to your CPU why that HashMap lookup just caused three cache misses, a page fault, and somehow triggered a garbage collection cycle in a language that doesn't even have one
Anonymous

Ah yes, O(1) - the algorithmic equivalent of 'assume a spherical cow in a vacuum.' We teach juniors that hash table lookups are constant time, conveniently omitting the part where cache misses, TLB thrashing, and the occasional cosmic ray turn your 'constant' operation into a probabilistic adventure. It's the lie that keeps our complexity analysis slides clean and our performance reviews awkward when production mysteriously slows down at 3 AM because someone's 'O(1)' data structure crossed a cache line boundary
Anonymous

Big O says my hash map lookup is O(1); perf says sure - after the page fault clears, the TLB miss recovers, the prefetcher guesses right, and the key isn’t on a remote NUMA node
Anonymous

Every O(1) hash table is really O(1 + cosmic rays)
Anonymous

O(1) exists on slides; in prod it’s O(1) if the key’s in L1 on the right NUMA node - otherwise it’s O(1) with a coefficient called TLB miss + GC pause + why is the prefetcher asleep?
@Vincent_Hawks 1y

O(1) is constant time access what are they yapping about smh
@rliskovenko 1y

n!
@mrYakov 1y

Lol, this man just dont know what computational complexity is.
@glicOne 1y

I can hear your gif
1. @mrell 1y
  
  I started hearing it too after I read your message)
@graduated_vernier 1y

When you are trying to sound smart without actually being smart.
@H3R3T1C 1y

God, O(1) not means 0ms of latency, means that the computational cost of an algorithm not depend of the input, for every input the time expend on the algorithm is the same, not 0ms
1. @CcxCZ 1y
  
  Not even same. Just not dependent on "n", whatever that means for given type of algorithm. Big Ο[micron] stands for asymptotic complexity, that is for very big (approaching infinity) values of n you will get complexity that approaches some function of n. This is specifically and deliberately defined in such way so you'd be able to ignore all the independent constant, and multiplicative factors as for large enough n they will be insignificant. https://en.m.wikipedia.org/wiki/Asymptotic_computational_complexity
  
  dev_meme 1y
  
  I would just refer to this meme from 2019 instead of explaining 😂 https://t.me/dev_meme/198
@H3R3T1C 1y

even two O(1) algorithm has differents running time
1. @paranoidPhantom 1y
  
  Sir do you have 3 citizenships?
  
  @V_3_R_B 1y
  
  Nix users have extra citizenship?
  
  @paranoidPhantom 1y
  
  Yes I believe that is one of the many benefits of using nixos
  
  @n3oney 1y
  
  NixOS supremacy of course
_ 1y

Part of the point seems to be that reading the input is considered instantaneous, otherwise any algorithm that actually needs it's whole input would be O(n). It also touches on the point that the time you need to read one byte depends where that byte is, and which bytes were accessed recently
@graduated_vernier 1y

I don't use any O or n variables in my code so I'm fine. ¯\_(ツ)_/¯
1. @SamsonovAnton 1y
  
  Neither do we use ^3 — but rather <3 of course!

Use J and K for navigation

The comforting lie of constant time complexity

Description

Categories

Common Tags

Comments

More like this

Binary Search Is Efficient, But Never Guess Her Age With It

O(n²) That Works vs O(n log n) Nobody Can Maintain

TCS Researchers Celebrate Their O(n^72649 lg^72(n)) Polynomial Triumph