Writing Recurrence Relations

[Music] finding the time complexity of recursive algorithms is not as straightforward as finding the space complexity of recursive algorithms which we have already understood in our previous chapter we are starting with this new chapter where we will learn how to write recurence relations for recursive algorithms and then ultimately solve and analyze our recursive algorithms in order to find time complexity and sometimes in order to find the return value and the number of operations of recursive algorithms we will learn all of these Concepts in this chapter so our focus of this chapter will be to analyze

recursive algorithms properly and to learn to find the time complexity return value and the number of operations so in this lecture our Focus will be on writing recen relations as we need to represent our recursive algorithms using recurrence relations to solve and analyze them so our first task in this journey is to learn to write recurence relations first we will understand what are recurence relations and then we will learn how to write reference relations for our recursive algorithms so let's get started with this lecture and let's see what are the topics the first topic of

this lecture is steps to analyze recursive algorithms we will first learn what are the steps involved in analyzing recursive algorithms and then we will proceed with writing the recurence relation of an algorithm as mentioned writing the recurence relation of recursive algorithm is important in order to analyze them so let's get started with the first topic steps to analyze recursive algorithms so here are the steps involved in analyzing recursive algorithms step number one is to write the recurrence relation of the algorithm we first need to write the recurrence relation of the recursive algorithm this means we

need to convert our recursive algorithm to its equivalent recurrence relation after writing the recurrence relation we need to solve the recurrence relation and we can solve the recurence relation using the one of the methods which we are available with we will learn those methods as we proceed in this chapter then the third step is to represent the recurrence relation using the ASM totic notation we then finally need to represent the result of the recurence relation that we obtain using the asymptotic notation so these are the steps involved in analyzing recursive algorithms we can find the

time complexity the return value even the space complexity and the number of operation ations easily by following these steps so now we know what are the steps involved in order to analyze our recursive algorithms let's move to the next topic where we will discuss how to write the recurrence relation of an algorithm remember this is Step number one so step number one is writing the recurrence relation of an algorithm precisely the recursive algorithm before we write the recurrence relation of recursive algorithm let's first understand what is the meaning of a recurence relation a recurence relation

is a mathematical expression that describes the overall cost of the problem in terms of the cost of solving the smaller sub problems now what does this definition mean a recurence relation is a mathematical expression so recurence relation is an expression which is a mathematical expression that describes the overall cost of the problem the cost can be time it can be return value it can be number of operations it can be space it can be anything so through recurrence relation we can describe the overall cost of the problem in hand in terms of the cost of

solving the smaller sub problems so through recurrence relation we can describe the overall cost of the problem that we have in terms of the cost of solving the smaller sub problems through recurrence relations we can easily find the cost of solving the problem in hand so it's a mathematical tool that helps us in doing this job now let's learn how to write the recurence relation for a simple algorithm as an example I am choosing the factorial algorithm this is the algorithm we are quite familiar with so I'm choosing this algorithm to write our first recurence

relation this algorithm is fact of N and we know that this is the base case if n is equal to 1 this means we are solving the problem of fact of one then we need to return 1 otherwise we need to return n * fact of n minus 1 this is the recursive case and in the recursive case we need to return n * fact of nus1 from fact of n we are calling fact of n minus1 now let us suppose that TN represents the time to solve fact of n let's say the cost that

we are considering here is time we are interested in finding the time complexity of fact of n so I'm assuming here that TN represents the time to solve all fact of n now let's relate this to the definition that we have a recurence relation is a mathematical expression that describes the overall cost of the problem what is the problem that we have here we want to find factorial of n so this is the problem that we have in hand we want to find how much time this algorithm will take this means we want to find

how much time it takes to solve fact of n we are representing this by T of n as T of n represents the time to solve fact of n so TN represents the overall cost in terms of time to solve fact of n so we have covered this part that is we described the overall cost of the problem by TN here cost is time I hope up to this point the concept is clear now what is the next thing that we need to do we need to represent this cost in terms of the cost of

solving the smaller sub problems now we know TN represents the time to solve fact of n now we need to represent TN in terms of the cost of solving the smaller sub problems this is a sub problem we know this represents fact of one if n is equal to 1 then one will be returned so this if block represents one sub problem and this L's block also represents a sub problem here we can observe from fact of n we are calling fact of n minus1 so we are reducing the problem by one here so in

comparison to fact of n this is a smaller problem therefore now we need to represent the if block and and the else Block in terms of T So indeed we will represent TN in terms of the cost of solving these smaller sub problems and that would complete the definition and eventually we would be able to get the recurrence relation which we want so now let's do this we know TN represents the time to solve fact of N and here we know this base case represents fact of one now we need to represent this base case

in terms of T this will be T1 because T1 represents the time to solve fact of one we know TN represents the time to solve fact of n so in order to solve fact of 1 T1 is the time needed and what is T1 equal to T1 is equal to some constant because checking the condition and returning some value takes constant amount of time so clearly the time required to solve this problem is T1 and T1 is equal to some constant C I'm assuming some constant by this Capital C I don't know the value of

C but I'm assuming T1 is equal to some constant so to solve fact of one we need constant amount of time because checking the condition and returning some value takes constant amount of time I hope this idea is clear so we have represented this smaller sub problem with the help of T now what's the next step we need to represent this L's block by T as well so let's do this here we have n * fact of n minus1 we have fact of n minus1 here we already know TN represent presents the time to solve

fact of n so in order to solve fact of n minus1 what do you think how much time it will take it will take T of n minus1 time because TN is the time required to solve fact of n clearly TN minus one will be the time required to solve fact of n minus 1 but what about this multiplication operation we are not only calling factor of n minus1 we are multiplying it by some n this multiplication will take constant time so T of nus1 will be the time required to solve factor of N minus1

and we need to add some constant time to T of n minus1 to represent the time required to complete this operation and not only this we are returning the entire result as well and as mentioned turning some value will also take some constant time so we can say this statement will take T of n min-1 plus constant time so this is the time required to solve this else block or in other words this statement T of n minus1 plus some constant Capital C it does not matter what letter I write here this C represents the

time required to perform this mathematical operation and to perform the return operation we know these two operations will take constant amount of time I'm representing This Time by C and T of n minus1 represents the time to solve fact of N minus1 and I got this from this TN because I know TN represents the time to solve fact of n so T of n minus 1 must be the time required to solve fact of n minus one and T of 1 represents the time to solve fact of one so now we have represented the cost

of solving the smaller sub Problems by T so what will be the overall cost we know TN depends on these two sub problems so the recurrence relation will be TN = to T of n - 1 + C if n is greater than 1 as we can observe in case of fact of n if n is greater than 1 then only the else block will execute if n is equal to 1 then the base case will execute or in other words the if block will execute so T of n is equal to T of n

-1 + C if n is greater than 1 if n is equal to 1 then T of n will be constant that is capital c so this is the recurrence relation which represents the overall cost in terms of time to solve fact of n now we can come to this definition once again a recurence relation is a mathematical expression this is the mathematical expression we can observe that describes the overall cost of the problem the the overall cost is TN in terms of the cost of solving the smaller sub problems these are the sub problems

so this is the recurence relation so obtained and recurrence relation can help us analyzing an algorithm we learned three steps required to analyze a recursive algorithm in order to analyze a recursive algorithm we represent it using the recurrence relation and then when we solve the recurrence relation in this case we will solve this recurrence relation which will help us find the time required to solve this algorithm and eventually we will represent the results so obtained using the ASM totic notation this will give us the time complexity of this algorithm I hope this entire idea is

clear why are we writing the recurrence relation of a recursive algorithm recurrence relation belongs to a recursive algorithm instead of analyzing the recursive algorithm directly we can represent it using the recurence relation like this and solving this recurrence relation is comparatively much easier this is the reason why we are writing the recurence relation so with this we are done with step number one writing the recurence relation of an algorithm we have completed step number one in in the next lecture we will learn how to solve the recurence relation that we obtained in this lecture so

with this we are done with this topic also writing the recurence relation of an algorithm and this means we are done with this lecture okay friends this is it for now thank you for watching this presentation I will see you in the next one [Applause] [Music]