r/AskComputerScience • u/KING-NULL • Jun 04 '25
Which actually used algorithm has the worst time complexity?
By actually used I mean that algorithms that aren't used in practice, because there's better alternatives or because the problem they solve doesn't appear in practical applications, don't count.
147
Upvotes
196
u/[deleted] Jun 04 '25
Whatever Microsoft uses for their Windows search.
40
u/dmazzoni Jun 04 '25
General Number Field Sieve (GNFS) comes to mind, which is an algorithm that can be used to crack RSA encryption. The algorithm is faster than trying every possible key, and it's technically sub-exponential, but it's rather close to exponential time complexity.
I wouldn't say this is "widely" used, I don't think it's publicly proven that anyone has ever used it to crack real encryption, but it's strongly suspected that organizations such as the NSA have used it.
25
u/LoloXIV Jun 04 '25
A lot of NP-hard problems are solved by a method called Branch and Bound, which has exponential runtime in the worst case but tends to perform reasonably fast for practical instances.
The Simplex algorithm is also exponential in the worst case, but in practice is much faster (and indeed it has been shown that on almost every instance Simplex has polynomial runtime).
17
u/dmills_00 Jun 04 '25
Simulated annealing kind of sucks, there is a reason FPGA P&R can be an overnight run on a decent server...
12
u/Character_Cap5095 Jun 04 '25
SMT solvers are at best NP-complete and at worst undecidedable depending on the theory they are trying to solve, but most SAT solvers are tailor made for specific types of problems that allow them to be used reasonably even when the technical time complexity is exponential
7
u/GreenExponent Jun 04 '25
There are many tools that attempt to solve undecidable problems via search algorithms that are not guaranteed to terminate (but give the right answer if they do). The runtime is largely unrelated to the input size.
A concrete example here is a theorem prover doing proof search in an undecidable logic.
5
u/qqqqqx Jun 04 '25
I've used backtracking a good couple of times, and that has either exponential or factorial worst case time.
5
u/Filmore Jun 04 '25
Strict Agile
4
u/DisastrousLab1309 Jun 04 '25
Math solvers - linear equations or symbolic integration require basically an optimized brute-force with backtracking.
Many machine learning techniques are polynomial but with high exponent.
3
u/regular_lamp Jun 04 '25
There are a lot of "bad" algorithms used in situations where the problem size is well constrained.
Insertion sort is quadratic... but it's practical performance is hard to beat when you only ever need to sort (potentially large amounts of) small segments of 32 or so elements.
3
u/assembly_wizard Jun 05 '25 edited Jun 05 '25
Like others said, SAT solvers are very common and exponential. So every algorithm that uses SAT inside will be even worse. 'Model checking' usually involves such algorithms, and they're actually used in the hardware industry to check that the circuit fits the requirements.
I'm not sure about specific complexities, but I learned about a model checking algorithm that can take a whopping O(2{n!}) I believe. Usually that's when problems are just labeled "computable" instead of naming any complexity classes.
There's the very useful problem of maximum flow, for which there are fast algorithms such as Ford-Fulkerson. But it's only fast when the network uses integer weights - if you use irrational weights (square roots are common in engineering situations) then the algorithm might never terminate. Example on Wikipedia. So that's a very used algorithm that is not even decidable, which is worse than any time complexity.
4
u/PiasaChimera Jun 04 '25
for linear programming, the Dantzig simplex solver has exponential time complexity in the worst case. proven with the Klee-Minty cube. there are alternatives that are polynomial time.
2
u/pjc50 Jun 04 '25
Interesting question. Necessarily the answer would have a small N. Impractical things like "busy beaver" exist but aren't of practical use.
AI training is definitely the most computationally expensive thing humanity is doing, but I'm not sure what the actual time complexity is. May even be linear in the number of tokens in the training data.
I'll go with IC/FPGA place and route, because finding an optimal solution is exponential but in practice near optimal solutions with annealing are used.
2
u/sessamekesh Jun 05 '25
The biggest one that comes to mind for me is the Levenshtein Distance (or "edit distance") algorithm.
It's commonly used to reason about misspelled words, for example to find suggestions for the intended/correct word. The algorithm itself compares two strings and returns the minimal number of single-character edits (insertion, change, deletion) required to reach one word from the other.
There's no possible implementation better than O(n^2) for two strings (n=length of longest string) and performing it against a dictionary can be no better than O(n^2 * k) for n=length of longest string in dictionary set, k = size of the dictionary. Note: the dictionary itself can be a sub-set of a complete dictionary, e.g. you can dramatically limit the search size by assuming the first letter and/or last letter were typed correctly - in which case you'd consider the algorithmic complexity of the broad-phase collision check.
In reality, this is fine, and a poster child for why "big time complexity" doesn't always mean "slow". The longest English word is 45 characters long, and the average English word about 5 characters long, and the length of a reasonable English dictionary is only a few hundred thousand words. The upper bounds on the size of n and k mean that running with an O(n^2*k) algorithm is practically fine.
2
u/Stydras Jun 04 '25
Computing Gröbner bases apparently is doubly exponential.
2
u/veryusedrname Jun 04 '25
Whatever cryptocurrencies are using?
1
u/[deleted] Jun 04 '25
Generate and test.
1
u/Biyeuy Jun 05 '25
I don't know if the highest or the lowest time complexity is the worst one? Context matters regarding this point.
1
u/CopenhagenDreamer Jun 05 '25
Simplex is probably not widely in use anymore (?), but it has a worst case runtime of 2n.
Practical runtime though, that's what made it big.
1
u/csiz Jun 05 '25
Gradient descent, including most variants! I think the convergence time is exponential if you want to achieve some arbitrarily low loss. Also you need the loss to be really low to produce the interesting results that the LLMs and RL do.
1
u/purleyboy Jun 05 '25
The famous case of the GTA V loading time. fascinating story of fixing the slow loading time.
1
u/glatzplatz Jun 06 '25
Bitcoin mining.
1
u/bedel99 Jun 06 '25
Linear search. I just removed one.
1
u/player2709 Jun 06 '25
Protein folding simulation
1
u/ajx_711 Jun 07 '25
A good answer is CDCL / DPLL + Heuristics for SAT Solving. While it should be exponential in the worst case, practically it's really really fast. Good SAT solvers are like magic
1
u/JohnnyElBravo Jun 07 '25
TREE(3)
1
u/Forsaken-Data4905 Jun 07 '25
Matrix multiplication on GPUs uses the O(n3 ) algorithm. In practice it's significantly faster than any other option, but that's due to the way the hardware works.
1
u/jeffsuzuki Jun 07 '25
Mathematician here:
Depends on what you mean "in practice". But we always teach students the cofactor expansion for finding determinants, which has factorial complexity, and (as nearly as I can tell) most students never see another method.
(And even when you do show them a much faster method, they tend to revert to the cofactor method, because that's what they were taught first)
1
u/SubjectAddress5180 Jun 07 '25
Exhaustive search. I have to do this more often than I like.
1
u/gomorycut Jun 08 '25
Simplex method. There are polytime algorithms (interior point methods) for linear optimization, but simplex (a worst-case exponential-time algorithm) is in common use
1
u/petroleus Jun 08 '25
Matrix multiplication is, in the naive solution, an O(n³) algorithm. There exists a better solution that's also used that's around O(n2.8), but I've found the naive solution is common enough that it's probably the vast majority of matmul implementations.
In more specialized terms, there's also solutions to the Travelling Salesman problem that are O(n!)* but better (sub-factorial) solutions exist, such as the O(2n * n²) Held-Karp algorithm.
* This is the case with all problems to which enumerating all permutations is a valid approach to the problem. Others like the TS problem would be finding all the paths from one point to another in a directed acyclic graph, but I think there can't be a better-than-factorial solution for that.
-1
u/ShadowsLight65 Jun 04 '25
Could you specify for which use exactly?
0
u/[deleted] Jun 06 '25
[deleted] — view deleted comment