problem I am
trying to find exact TC of my code
https://practice.geeksforgeeks.org/problems/longest-common-subsequence-1587115620/1
my code >>https://ide.codingblocks.com/s/574663
is time complexity O(2pow(len(s1)+len(s2))) or
O(2pow(len(s1)*len(s2))) ???
It will be neither of these, because your TC is decreased due to using memoization. For bottom up solution the TC is O(n*m)
I guess we can find it’s TC considering worst case when all elements are distinct in sequence 1 and sequence 2 . so in respect to this case can u help me to find it ?
O(m*n) is in worst case only. Do you want to find recursion complexity of with or without memoization?
Recursion one bcz I think in that case it will become O(2^(len(s1)+len(s2))) ?? right?
Yes it will be exponential in that case, but since you are using memoization the time complexity will decrease significantly
ma’am I meant without memoization !!
I think i have answered that above, it will be exponential
okay got that thankyou so much !!!
one more thing most of times when we write Top down solution using memoization we say TC is exponential bcz it is but when we transform the same recursiove solution to bottom up method we usually use 2 for loops depending on ques and deduce time complexity is O(n^2) well can u help me bit in this !!!
Time complexity of recursive/top-down is exponential only without memoization, it is reduced when you use memoization! So its hard to actually visualise what the TC will be in that case. But you can easily tell in bottom up solutions
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.