Re:Node.js 14 is over 20x faster than Python3.8 for fib(n)
by maxmaio on Tuesday February 09, 2021 @01:33PM
(#26080967)
I know it's not super relevant to node vs python3, but your fib(n) has a time complexity of O(2^n)... with a dp approach it can be solved in O(n). also your space complexity can be reduced to O(1).
[ Parent
| on HN ]
Re:Node.js 14 is over 20x faster than Python3.8 for fib(n)
by contravariant on Tuesday February 09, 2021 @03:34PM
(#26082103)
With a better chosen dp approach you can even solve it in O(log(n)). Though at that point the extra cost of multiplying large integers becomes non-negligible.