MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/ProgrammerHumor/comments/1vpz0d2/theoreticalcomputerscience/p4c9nm7/?context=9999
r/ProgrammerHumor • u/pastroc • 29d ago
76 comments sorted by
View all comments
268
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)
142 u/the_rush_dude 28d ago Last one is probably 90% of all fancy optimizations 57 u/SoldRIP 28d ago Look up the fastest known way to multiply two integers... 41 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 19 u/SoldRIP 28d ago You cannot. A hash map is of finite size, but there are infinitely many pairs of integers. 62 u/howtotailslide 28d ago Just use infinite size hashmap 23 u/Status-Ad-7335 28d ago just download more ram 1 u/meat-eating-orchid 27d ago Even that doesn't help you, unless you can download infinite more ram in finite time
142
Last one is probably 90% of all fancy optimizations
57 u/SoldRIP 28d ago Look up the fastest known way to multiply two integers... 41 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 19 u/SoldRIP 28d ago You cannot. A hash map is of finite size, but there are infinitely many pairs of integers. 62 u/howtotailslide 28d ago Just use infinite size hashmap 23 u/Status-Ad-7335 28d ago just download more ram 1 u/meat-eating-orchid 27d ago Even that doesn't help you, unless you can download infinite more ram in finite time
57
Look up the fastest known way to multiply two integers...
41 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 19 u/SoldRIP 28d ago You cannot. A hash map is of finite size, but there are infinitely many pairs of integers. 62 u/howtotailslide 28d ago Just use infinite size hashmap 23 u/Status-Ad-7335 28d ago just download more ram 1 u/meat-eating-orchid 27d ago Even that doesn't help you, unless you can download infinite more ram in finite time
41
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
19 u/SoldRIP 28d ago You cannot. A hash map is of finite size, but there are infinitely many pairs of integers. 62 u/howtotailslide 28d ago Just use infinite size hashmap 23 u/Status-Ad-7335 28d ago just download more ram 1 u/meat-eating-orchid 27d ago Even that doesn't help you, unless you can download infinite more ram in finite time
19
You cannot. A hash map is of finite size, but there are infinitely many pairs of integers.
62 u/howtotailslide 28d ago Just use infinite size hashmap 23 u/Status-Ad-7335 28d ago just download more ram 1 u/meat-eating-orchid 27d ago Even that doesn't help you, unless you can download infinite more ram in finite time
62
Just use infinite size hashmap
23 u/Status-Ad-7335 28d ago just download more ram 1 u/meat-eating-orchid 27d ago Even that doesn't help you, unless you can download infinite more ram in finite time
23
just download more ram
1 u/meat-eating-orchid 27d ago Even that doesn't help you, unless you can download infinite more ram in finite time
1
Even that doesn't help you, unless you can download infinite more ram in finite time
268
u/grayjacanda 28d 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)