2.1.1 Recurrence Relation (T(n)= T(n-1) + 1) #1

hi in this video we'll learn how to trace the recursive function and how to write a recurrence relation and how to solve a recurrence relation so I am taking one of the example then in the other videos you can find following examples more examples will come in other videos let us start already I have an algorithm our function here or C language function I have written you call it as algorithm also test is a function which is taking n as input and if n is greater than 0 it is printing the value and then it is calling itself for n minus 1 so I will take some sample value and test it suppose I am calling this function by passing 3 let us see what happens if I pass 3 test 3 3 is greater than 0 yes 3 is greater than 0 print 3 so it will print 3 then call itself 4 3 minus 1 that is true so call test 2 then for 2 again it's a recursive call so for this call it will print 2 and call itself for 1 1 is greater than 0 so it's very gutsy call again for this one as it is greater than 0 it will print 1 and call itself for test 0 now when it is 0 0 is not greater than 0 so it will not call itself and it will stop doesn't go further so this is a tracing tree for this particular function or recursive function I have passed a 3 so what is the time taken by this one so let us see what it is doing and this call it is printing a value then calling again printing a value and calling again printing a value and calling again so the amount of work done is just printing value how many times it is printing this is the major work done by this function printing a value how many times it is doing three times it is doing as I have passed a three how many times it is calling itself as I have given three it is calling itself four four times now what is the time taken for printf it is just one unit of time just a single statement and simple statement it is taking one unit of time if I say one unit of time then in each call it is spending one unit of time that is printing and then calling so one unit of time one unit of time so total how much time it has taken three if I take number of calls then there are four that is three plus one it means if I pass five then it will be five plus one calls and five is the number of time it is will it will print so if I pass n that total how many calls it will make it will make n plus 1 calls n plus 1 cons and how many times printf is executed and dimes if I approximate the amount of work done depends on the number of calls if I say like in the last call it is not printing just ignore that and say that for every call it is printing so the time depends on what it depends on the number of calls so how many calls it will make for any n it will make n plus 1 calls so the time function if I write F of n then it is n plus 1 then what is the time complexity in notations its order of n I can use Big O of n theta of N or Omega often anything I can write there this we have already discussed in previous videos so that's it by a tracing tree I have found the complexity of this one you can also call it as a recursive tree or a tracing tree or a recursive tree I have used now let us find out how to prepare a recurrence relation for this function and how to solve that recurrence relation now if any function or an algorithm is given to you you can prepare a recurrence relation as follows like this I'm showing you assume that the time taken by this is f of n no usually for recurrence relation function name is a T that is T often su so I'll use the same thing so instead of F of n I'll call it as T of n time taken by this algorithm st and/or this function is T n then that TN will be equal to what the total amount of time taken by this one so let us observe what is happening inside condition is checked that a signal condition inside that printf is there one it will take one unit of time the next what is the next one it's a recursive call it's the same thing how much time we mentioned for this T and then what will be the time for this one T and minus one right now that's it so what is the total time TN I said that the total time taken by this part of an algorithm so that TN is equal to TN minus 1 plus 1 now you can ask me why you have ignored condition say if I consider that condition also for one time then it is just one condition so one time then I will get 2 here if I take 2 also then the result of this result of this expression will be same only for the recurrence relation I will get the same answer so if you have any constant value you can simply make it as 1 and or if you can write it as see also and use it constant or some a as a constant some constant also you can write and use it so I prefer taking it as one so if you have more than one then you can round it up to one only all right this is the way we write a recurrence relation now let us write a recurrence relation T n is equals 2t n minus 1 plus 1 this one when when n is greater than 0 yes when n is greater than 0 this is the time what happens if n is equals to 0 it's not doing anything if n is equals to 0 so if n is equals to 0 it is not doing anything shall I write 0 here no the time we don't write it 0 if it is 0 also it is a constant so we write it as 1 so I will take it as 1 or else you can make it as C or a or K anything some constant you can write there now let us solve this recurrence relation now let us solve this recurrence relation by a substitution method back substitution we will follow let us take this this is T and is equals to T n minus 1 plus 1 we will solve this one that is already solved it is 1 we have to solve this one now for solving this I can know the answer for TN if I know what is TN minus 1 so what is TN minus 1 what is this if I know I will use it here so I don't know TN minus 1 but I know what is the TN TN is equals to T n minus 1 plus 1 yes this is the 1 then what will be TN minus 1 so if this is n by N and change to n minus 1 so this also n minus 1 so this becomes n minus 1 minus 1 and minus 2 plus 1 okay since this is T n therefore TN minus 1 is this one now substitute TN minus 1 in this equation so T n is equals to n bracket I'll write this TN minus 1 so what I got T n minus 2 plus 1 and plus 1 so this part I have substituted here at this place so I got this funny that this is T n is equals to T n minus 2 plus 2 1 plus 1 2 if I substitute again then T n is equals to what will be T n minus 2 T n minus 3 plus 1 see this T n minus 2 will be equal to e and minus 3 plus 1 yes I have substituted this portion here right at this place so I have written this then plus 2 is as it is now if I solve this one again then T n is equals to T n minus 3 plus 3 that's what I got so how many times I should do this see when I got two times that is sufficient you can continue further and I say that I am going to continue this how long for K times continue for K times if I continue 4k times what I get see if you observe when I did for one time it was - next time it was three then it goes on so it will be K so this will be T n is equals to T n minus k plus K so this is the important one for me now I'll continue here what is the equation I got T M is equals to T and minus k plus key see it was T n minus 1 plus 1 substituted I got TN minus 2 plus 2 substituted I got TN minus 3 plus 3 continued up to K so D and minus k plus K this one so I said that I will stop at K came in some some steps after some steps I will stop after K steps k substitutions I will stop now what is the smaller value I know I know n is equals to 0 if n is equals to 0 I know but it's 1 answer is 1 so here and the minus 1 was there so minus 2 then 3 then 4 if you go on subtracting like this at one point it should become 0 so the my purpose was to substitute on substitute and we still n equal to 0 so I assume that I have reached at 0 so I assumed this and minus K is 0 not even this means I have reached till there when I say anything minus K is equals to 0 therefore n is equals to K then what this will be this will be T n is equals to e and minus n plus n then TN is equals to what is this t 0 plus n so this is what is it easy to easy to be already know and it is 1 plus n that's it it is solved what the answer I got you see 1 plus n is the time so just now I have shown you how we can prepare a recursive tree and find the time for that algorithm I actually made a tracing as well as along with that recursive tree so there also a garden bliss phone calls here also I am getting the answer as in plus 1 so I have prepared a recurrence relation solve that recurrence relation and I got this answer and this is again order of n see actually this belongs to a class linear class order of n that is n so I can call it as theta of n that's it this is the first week of installation so I will show you more and more recurrence relation so I'll take the program I will prepare the recurrence relation and I will solve it so continue watching rest of the videos

Channel: Abdul Bari

Views: 766,471

Rating: 4.9401598 out of 5

Keywords: Algorithm, Algorithms, Recurrence Relations, Back substitution, induction, abdul bari, bari

Id: 4V30R3I1vLI

Length: 13min 42sec (822 seconds)

Published: Mon Jan 22 2018