« first day (1117 days earlier)   

vzn
1:28 AM
@evinda nearly any nontrivial problem/ algorithm would probably work as a counterexample. a nice algorithm in this area, try fibonacci sequence. what can you say about memoization & recursion vs bottom-up in general? eg for fibonacci? do any of those terms mean anything to you?
see your participation in Mathematics... are you in undergraduate CS?
 
1:49 AM
@vzn Hello :) I am an undergraduate student in applied mathematics. What's with you? :)

If we want to calculate the Fibonacci sequence fib(n) with memoization and recursion, we woud call this, and it would call fib(n)=fib(n-1)+fib(n-2), which would call fib(n-1)=fib(n-2)+fib(n-3) and so on, which would call fib(2)=fib(1)+fib(0)=1+0=1. Then it would finally resolve fib(3)=fib(2)+fib(1), but it doesn't need to recalculate fib(2), because we cached it, then it will resolve f(4)=f(3)+f(2), but it doesn't need to recalculate fib(3) and so on...
 
 
7 hours later…
8:38 AM
@evinda From what I know, Time complexity and space complexity would be same. But in case of fibonacci you can optimise dynamic programming solution by caching only last two elements while iterating and that will reduce the space complexity to constant and same time complexity as before.
 

« first day (1117 days earlier)