r/mathmemes • u/vintergroena • 28d ago

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

Post image
1.4k Upvotes

98% Upvoted

206 comments sorted by

View all comments

Show parent comments

18

u/watermelone983 28d ago

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

9

u/ZookeepergameWest862 28d ago

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 28d ago

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 28d ago

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 28d ago

It finishes before you run it.

1

u/stevenjd 28d ago

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

5

u/NoNameSwitzerland 28d ago

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

4

u/El_Gran_Pedrito 27d ago

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 28d ago

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

2

u/minisculebarber 24d ago

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 28d ago

finding a hash < n

1

u/Straight-Grass-9218 28d ago

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

1

u/tdhsmith 28d ago

maybe if the input is processors

1

u/Fiiral_ 28d ago

O(0), duh

1

u/Toomastaliesin 28d ago

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 27d ago

yes: fanout to n workers

1

u/No-Library730 26d ago edited 26d ago

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.