Re:Efficient algorithms, the Exponential Time Hypothesis, an...
by aleph_minus_one on Tuesday November 03, 2026 @06:25AM
(#50350642)
> It's completely standard for "galactic" algorithms and not relevant to big-O runtime.
This is true, but if doing brute-force search for all instances below some super-astronomic threshold is part of the algorithm, you typically want to understand
- where this constant comes from,
- how much this constant can be decreased (or why it can't)
- etc.
So, proving the correctness of an algorithm which is doing brute-force search for all instances below some super-astronomic threshold is typically just the first step towards getting an understanding of the complexity-theoretic phenomenon.
So: There is indeed nothing wrong with such aspects of galactic algorithms, but exactly understanding and improving the super-astronomic thresholds involved is the next step.
This is true, but if doing brute-force search for all instances below some super-astronomic threshold is part of the algorithm, you typically want to understand
- where this constant comes from,
- how much this constant can be decreased (or why it can't)
- etc.
So, proving the correctness of an algorithm which is doing brute-force search for all instances below some super-astronomic threshold is typically just the first step towards getting an understanding of the complexity-theoretic phenomenon.
So: There is indeed nothing wrong with such aspects of galactic algorithms, but exactly understanding and improving the super-astronomic thresholds involved is the next step.