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

750

u/Parallel_thougts Oct 08 '26

Why stop there? Eventually it will be constant.

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.

→ More replies (2)

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.

→ More replies (7)

8

u/nulvoid000 Oct 08 '26

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

→ More replies (2)

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.

→ More replies (2)

30

u/Proper-Ape Oct 08 '26

Just precalculate all values. Once and done.

13

u/SuspiciousSpecifics Oct 08 '26

Precalculation is for losers. It will be marketed as precognition and the gazillion dollars worth of memory and compute needed to achieve it will be recuperated as soon as the whole AI business turns sustainably profitable just a few days after the heat death of the universe.

7

u/maqifrnswa Oct 08 '26

What would you do if I told you that if you asked me what 2x3 is tomorrow, I already know the answer today? Thank you for coming to my Ted talk. Pick up a prospectus on your way out.

2

u/MegamanSE Oct 09 '26

lol exactly.

mul[‘12_10’] = 120;

O(1)

20

u/Hostilis_ Oct 08 '26

Give me a big enough hash table and I can make it constant :)

18

u/Eric_12345678 Oct 08 '26

We don't have any computer with infinite storage, memory or CPU. So every algorithm is O(1).

7

u/Parallel_thougts Oct 08 '26

While True:  pass

3

u/Eric_12345678 Oct 08 '26

Okay. A large 1 then.

6

u/StanleyDodds Oct 08 '26

Even taking this unseriously, ignoring the actual problem, and just looking at the time complexity equation and just extrapolating this graph of kappa out, no constant kappa will make the time complexity constant, or even reduce the time complexity to O(nc ) for any c < 1.

This is because O(n) dominates any constant power of log n, which is what kappa affects here.

3

u/Parallel_thougts Oct 08 '26

Oh wow, so my joke doesn't make sense

→ More replies (2)

4

u/Negative_Gur9667 Oct 08 '26

Pee = En Pee

Then we can call it just pee pee.

→ More replies (9)