what will be the number of recursive calls and depth of stack required to implement lis using top down approach with and without memoization?
Minor issues in analysis of lis
With memoization, there are atmost n^2 states(Space complexity is O(n^2), so clearly maximum number of recursive calls will be n^2. Same will be the depth of stack.
Without memoization the number of recursive calls will be 2^n. (Bacause At each index i(from 0 to n-1), there are 2 choices-> either LIS ends at index i or does not end there). So same will be the depth of stack.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.
is depth of stack will be O(n) or O(n^2).how is it the latter.please give the recursion tree for that.