Two production incidents at Sentry were caused by O(n^2) algorithms that passed testing but failed with larger datasets. The Android case involved DEX file symbolication where a linear scan fallback created quadratic complexity with 52,202 classes, solved by adding a dictionary lookup. The iOS case involved LIEF library's export trie parsing with an unpopulated cache causing linear scans, fixed with a simple patch. Both demonstrate how O(n^2) algorithms are fast enough to reach production but slow enough to cause failures at scale.
Sort: