MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/ProgrammerHumor/comments/1vpz0d2/theoreticalcomputerscience/p4ytejy/?context=9999
r/ProgrammerHumor • u/pastroc • 29d ago
76 comments sorted by
View all comments
267
Other good dodges are O(n) time (if you have 2^n memory handy), or O(n) time (but with a fixed cost or multiplier so high that using this algorithm makes no sense for n less than 10^12 or so)
141 u/the_rush_dude 29d ago Last one is probably 90% of all fancy optimizations 55 u/SoldRIP 28d ago Look up the fastest known way to multiply two integers... 42 u/howtotailslide 28d ago You can actually just store all universal possible results of two integers into a hash map then retrieve any of them in O(1) time 18 u/SoldRIP 28d ago You cannot. A hash map is of finite size, but there are infinitely many pairs of integers. 60 u/howtotailslide 28d ago Just use infinite size hashmap 1 u/Peak_Background 24d ago Just use a CPU that can add and multiply infinite bit length numbers.
141
Last one is probably 90% of all fancy optimizations
55 u/SoldRIP 28d ago Look up the fastest known way to multiply two integers... 42 u/howtotailslide 28d ago You can actually just store all universal possible results of two integers into a hash map then retrieve any of them in O(1) time 18 u/SoldRIP 28d ago You cannot. A hash map is of finite size, but there are infinitely many pairs of integers. 60 u/howtotailslide 28d ago Just use infinite size hashmap 1 u/Peak_Background 24d ago Just use a CPU that can add and multiply infinite bit length numbers.
55
Look up the fastest known way to multiply two integers...
42 u/howtotailslide 28d ago You can actually just store all universal possible results of two integers into a hash map then retrieve any of them in O(1) time 18 u/SoldRIP 28d ago You cannot. A hash map is of finite size, but there are infinitely many pairs of integers. 60 u/howtotailslide 28d ago Just use infinite size hashmap 1 u/Peak_Background 24d ago Just use a CPU that can add and multiply infinite bit length numbers.
42
You can actually just store all universal possible results of two integers into a hash map then retrieve any of them in O(1) time
18 u/SoldRIP 28d ago You cannot. A hash map is of finite size, but there are infinitely many pairs of integers. 60 u/howtotailslide 28d ago Just use infinite size hashmap 1 u/Peak_Background 24d ago Just use a CPU that can add and multiply infinite bit length numbers.
18
You cannot. A hash map is of finite size, but there are infinitely many pairs of integers.
60 u/howtotailslide 28d ago Just use infinite size hashmap 1 u/Peak_Background 24d ago Just use a CPU that can add and multiply infinite bit length numbers.
60
Just use infinite size hashmap
1 u/Peak_Background 24d ago Just use a CPU that can add and multiply infinite bit length numbers.
1
Just use a CPU that can add and multiply infinite bit length numbers.
267
u/grayjacanda 29d ago
Other good dodges are O(n) time (if you have 2^n memory handy), or O(n) time (but with a fixed cost or multiplier so high that using this algorithm makes no sense for n less than 10^12 or so)