Previously we have discussed how to successfully solve this question.
Now let's take a look at the complexity analysis, or the time and space complexity of the solution
that we came up with.
Now for this, let's take a quick example.
Let's say we want to find the character or the value at the eighth index in the fourth row.
So n is equal to four and k is equal to eight.
Let's quickly draw the recursion tree for this over here to get an idea of what the time and space complexity
is of the solution that we came up with.
Now, if we want to find n is equal to four and k is equal to eight, because over here k is eight,
which is in the second half.
And the corresponding element for this in the previous row would be eight minus the midpoint which is
four.
Right.
So that's this over here.
And we would take note of this.
So to find four comma eight as we have discussed the solution or the recursive function would try to
find the value of three comma four and then find north of this.
Right.
So that's how the solution works.
And to find three comma four because again this is in the second half we would find two f of two comma
two and then find north of it.
Right.
So that's how the solution works.
And to find two comma two this is two comma two.
We would go ahead and find one comma one.
So this is how it works right.
And again for this also because it's in the second half two comma two is in the second half we would
find north of this.
And this is how the solution works.
So again quickly revising one comma.
One in this case is zero.
North of it is one.
So this would return one.
And.
Two.
This is one, so this becomes one.
And not of one is zero.
So this returns zero.
So this becomes zero and not of zero is one and it returns one.
So that's how we get the value as one which is what we have over here.
Now over here.
Notice that the number of operations done over here is of the order of N.
Right.
So we can say that the time complexity is of the order of n because we have one, two, three, four.
Again, remember the time complexity of a recursive solution can be found as the number of nodes that
we have in the recursion tree into the work done in each node.
Now over here, notice that the number of nodes that we have is of the order of n, because we had over
here n as four.
And notice we had four nodes in the recursion tree, and in each node we are doing some constant time
operations, like we are finding the length of that particular row.
And we are comparing whether k is in the first half or the second half, which are constant time operations.
So that's why the time complexity is of the order of O, order of n into one, because inside each node
we are just doing constant time operations.
So we have seen that the time complexity of this solution is of the order of n, and the space complexity
is also going to be of the order of n because of the recursive call stack.
Okay.
So again let's visualize the recursive call stack over here.
Initially we would be calling the function with the parameters n as four and k as eight.
This would call f of three comma four.
And again notice that four comma eight is not yet completed.
So the computer has to hold on to this.
And then three comma four would recursively call two comma two.
And this would recursively call one comma one.
And then this will start returning right.
So this would pop up and then this would pop and return.
And this would pop and return.
And finally this would also pop and return.
So notice over here the maximum number of calls at any point was four, which is of the order of n because
n was four in this case.
So that's why the space complexity of this solution is also of the order of n.