4 ms·
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 sp
by maxmaio 6y ago
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).
- contravariant 6y agoWith 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.
- maxmaio 6y agoI'm having trouble coming up with this approach on my own. could you share it please?