Hey there and welcome back!
In the previous videos, we have discussed the tabulation approach by just using a one dimensional array
for solving the Liz question.
Let's now take a look at the space and time complexity of the approach that we have come up with.
So the space complexity is obvious.
It's going to be of the order of N because we have to have this DP table.
And again we are not using any recursive call stack space because the solution over here is an iterative
one.
So the space complexity is of the order of n.
Now when it comes to the time complexity, it's still going to be of the order of n square.
Now why is that the case?
Remember initially when I was equal to one, we had to do one operation because j took the value zero.
And then when I is equal to two, j will take the values zero and one.
That's two operations.
Then when I is equal to three, j will take these three values.
So that's three operations.
So the total number of operations that we would have to do will be one plus two plus three etc. up to
n minus one which equals n minus one into n divided by two.
Now this over here when you simplify it there will be an n square term.
And that's why because that is the dominating term.
The time complexity of this approach is of the order of n square.
So these are the approaches that we have discussed for the Liz question.
Now the bottom up 1D approach has a space complexity of the order of N and the time complexity of the
order of N square.
Now notice that the time complexity over here is much better than the time complexity that we had achieved
with just recursion, and the space complexity over here is also of the order of N, which was the space
complexity that we had used up over here.
But again, we are not using recursive call stack space.
So that's an added advantage as this solution is an iterative one.