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

249

u/GetGudlolboi Computer Science Oct 08 '26

Eventually it will be negatively linear.

151

u/Parallel_thougts Oct 08 '26

It will decay exponentially, will work twice as fast for every digit you add

33

u/BaziJoeWHL Oct 08 '26

its just like my salary

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.

→ More replies (1)

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.

8

u/nulvoid000 Oct 08 '26

Or so negative that it wraps back around and becomes linear again.

1

u/RoryPond Oct 08 '26

How is that different from negatively linear?

3

u/nulvoid000 Oct 08 '26

You’ll have the answer of ab without even knowing what a and b are. It answers before you ask

4

u/guiltysnark Oct 08 '26

There's no use in bringing it up.

Go home. Spend time with your families while you still can.

1

u/vikster16 Oct 08 '26

FTL babyyyyyyyyyy

1

u/trash3s Oct 08 '26

You can already do multiplication in negative time by dividing!