Timeline for computational complexity: do we gain acceleration?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 16, 2017 at 20:01 | comment | added | Kevin Buzzard | Actually, I think that for the case in question it's a complete no-brainer. For the 3-step sum by the time you've taken 20 terms you're correct to about 37 decimal places, and for the first sum it would take something like $10^{12}$ terms to get that far. I am pretty confident that you can compute 80 choose 20 in fewer than $10^{12}$ steps :-) | |
| Jan 16, 2017 at 19:53 | comment | added | Kevin Buzzard | I would imagine that computing the number of operations required isn't easy in general, especially if there are tricks which you don't know. How many operations does it take to compute (4n choose n) * (3n choose n), for example? Probably some ways are better than others. | |
| Jan 16, 2017 at 18:15 | history | answered | Federico Poloni | CC BY-SA 3.0 |