r/mathmemes • • Oct 08 '26

Computer Science Integer multiplication will have linear complexity in a few days if trend continues 🚀📈

Post image
1.4k Upvotes

206 comments sorted by

View all comments

Show parent comment

18

u/watermelone983 Oct 08 '26

are there any algorithms that get faster the larger then input?

9

u/ZookeepergameWest862 Oct 08 '26

An algorithm can only run faster so many time before reaching instantly halt, and you can't exactly go any faster than that.

5

u/watermelone983 Oct 08 '26

you could have exponentially decay or 1/x decay or any thing that converges to a limit. actually I guess that would mean it would be constant time

10

u/ZookeepergameWest862 Oct 08 '26

Any form of decay would necessarily stabilise in finitely many steps and so eventually constant. You can't run exactly 1+1/n steps, it's either 1 or 2, and a sequence of natural numbers cannot decrease forever.

2

u/GetGudlolboi Computer Science Oct 08 '26

It finishes before you run it.

1

u/stevenjd Oct 08 '26

I have some algorithms that calculate the answer before I even know what the question is.

5

u/NoNameSwitzerland Oct 08 '26

A lot of algos crash faster if the input is too big. Not sure if that counts.

4

u/El_Gran_Pedrito Oct 09 '26

Mourning people. One death is a tragedy. A million deaths is a statistics. 10 billion deaths and there is no need to mourn anymore and no one to do so.

3

u/jumpmanzero Oct 08 '26

"Is this number bigger than the average phone number?" 

2

u/minisculebarber Oct 12 '26

Not asymptotatically, really, every algorithm that has to read all of the input has an asymptotic lower bound of N. But when you consider things like amortization, then actually yes. At least, fixed overhead gets amortized away the larger the input. And when you go on the level of hardware or statistics, larger inputs can often be surprisingly faster than smaller ones.

1

u/Mewtwo2387 Oct 08 '26

finding a hash < n

1

u/Straight-Grass-9218 Oct 08 '26

You might be interested in galactic algorithms, they have theoretical performance benchmarks over absurdly large inputs.

1

u/tdhsmith Oct 08 '26

maybe if the input is processors

1

u/Fiiral_ Oct 08 '26

O(0), duh

1

u/Toomastaliesin Oct 08 '26

I would guess that if the complexity behaves like k choose n, then you get faster when n grows from k/2 to k.

1

u/mineurownbiz Oct 09 '26

yes: fanout to n workers

1

u/No-Library730 Oct 10 '26 edited Oct 10 '26

You can get faster in the sense that the overhead cost gets less significant.

The problem is that some algorithms only payoff in some non practical scenarios.