2.1.3 Recurrence Relation (T(n)= T(n-1) + log n) #3

hi already I have two videos on recurrence relation there I have shown the steps in detail now here I will do it little quickly right so all you also get the idea how we can do it quickly right I'll just skip some steps that's it right not direct answer let us state this is an algorithm or a function we have to find out how much time it is taking so we know that this will take T and the time now there is a loop if you observe this is I starting from 1 and I assign I into 2 so this is x 2 every time so by looking at the loop you should know what is the time taken by this statement already we have seen this in examples of time complexities one video is there you can watch that one I have shown how to find directly know what is the time taken by this one so we know that this statement will execute for log n time now I will not consider this one and this one if I consider also again I have to take the degree of expression and the degree will be log in only this will be log n plus 1 this is 1 so 2 log n plus 2 again I have to write log in only so let us just concentrate on only this is statement this will is the main thing that is printing the algorithm is doing nothing just printing the value so the job of printing we are constructing that one its login then how much this one and this is T n so this is T n minus 1 what is total for this one so this is e n is equals to T n minus 1 plus log n TN minus 1 plus log in that TN is equals to so and so the stayin is sum of these two now what is the recurrence relation TN is equals to 1 if n is 0 this is common you have seen in previous algorithms also I will not explain them then this is T and minus 1 plus log n for N greater than 0 now I will solve this one using tree method so if I take Tian Tian what it is doing its taking log and time and it is calling itself for TN minus 1 then what this will do this will take log n minus 1 time and call itself for n minus 2 then this will be log n minus 2 and call itself for n minus 3 goes on so at one point it will be what t2 said and it will look log 2 times and it will call itself for 1 and this will be log 1 and this will call itself for T 0 so this will stop at 0 when n becomes 0 they will stop there now what is the time taken in each step log in here this is log n time in this call log n minus 1 time in this call like this so this total is I will take few terms only log n plus log n minus 1 plus goes on to log 2 plus log 1 this is the summation of the time taken in each call what is this equal to this is log n into n minus 1 into goes on to 2 into 1 I'll write this in square brackets so what is this n into n minus 1 into so on - 2 into 1 so it is just like 1 into 2 into 3 into 2 n so this is nothing but log n factorial so here I write log n factorial log in factorial already we know this there is no tight bond for this one but there's an upper bound for log n factorial for n factorial upper bound is n power n so for log n factorial log of n power n that will be equal to Big O of n log n so that's it this is the time we got so the time taken by this algorithm is n log in and log n right so this is with the tree method I have shown you so you got the time complexity as n log n now by using induction method I will solve this recurrence relation I will remove this and I will solve that one directly let us solve this recurrence relation by induction or substitution method so I write this recurrence relation P n is equals to T n minus 1 plus log n then directly I'll write down this will be what TN is equals to in place of this what it will be T and minus 2 plus log of n minus 1 plus this log in as it is this was the first equation now if I simplify this one open the brackets T n minus 2 plus love of n minus 1 plus log in then this is the second one I got that I will substitutes 1 so this will be T n is equals to in bracket TN minus 2 will be TN minus 3 plus log and minus 2 plus these terms as it is log n minus 1 plus log n this is in brackets I'll open this one so T n is T n minus 3 plus log of n minus 2 log of n minus 1 plus log this is the third one if I continue for K times then what will happen see this was end and n minus 1 then n minus 2 so it will be going on reusing up to 1 so directly ever I don't so here I continue so TN will be equal to T and minus K plus log 1 plus log 2 plus goes on to log n minus 1 plus log now we know that n minus K is equals to 0 therefore n is equals to K now if I substitute there TN is equals to this becomes D 0 and all these terms if I add I am getting same terms so this is log n factorial now I'm not sure how to get that already we have seen this in the previous method this is 1 plus log and fat oh really what is time taken in this one this is Big O of n log n that's it we got the same answer that is Big O of n log and that is log n factorial now if you have already seen first in the second video for recurrence relation with decreasing functions this is the third video if you have already seen those two then you can understand this now I'm going to show you how we can directly get dancer for a recurrence relation of decreasing functions see I will take the examples of first two videos then also this one then let us see see there I just write a simple expression t n-1 t and minus 1 plus 1 and the time taken in this one was and just say order of not be go theta anything to sort ruffman's just the degree i am writing this answer was n and the second video we have seen this T and minus 1 plus n so this was n square and at the third video this one in this video just now we have seen this TN minus 1 plus log N and this is n log n so what do you understand from this one so when this is T of n minus 1 means n is a decreasing and this is decreasing every time so if it is 1 multiplied by n what is n multiplied by an n Square log and multiplied by N and log in so it means we can make out that if recurrence relation is TN minus 1 plus n square then it will be definitely into n so this is n cube yes this is true right so whatever the term you are having here just multiplied by n because this is going to repeat for n times so that's why this whole thing can do and if from the first one I'm just making some change T and minus 2 plus 1 instead of n minus 1 plus 1 it is minus 2 plus 1 so the exact answer you will be getting as n by 2 because it is taking to two steps every time instead of 1 1 step 1 1 value decremented to to Valdosta chromatic so it will be n by 2 that is again order of n only means that even if you have TN is equals to T and minus hundred plus and then what will be the answer as this is n just multiplied by n first order of n square this is n minus not 1 n minus 1 it's n minus entered whatever it may be so it is taking hundred step every time plus hundred so imagine n value as in 10 thousands or millions a bigger very very big value of for small values you can say that no no it will not take that much time big values of n so we say that whatever the value of n may be from some value to infinity will go so yes this is true so whatever you subtract that you get the same answer but if you have a recurrence relation like this 2 will do T of n minus 1 plus 1 if there is some coefficient here then it's not directly 1 into n so we'll see what will happen in this one right see there were no coefficients here there were no coefficients only these values were changing 1 n log n n Square and cube and log n anything so whatever you have here just multiply it by and write but now if there is a coefficient then what should be done so you will see this in next video next to this one right

Channel: Abdul Bari

Views: 318,780

Rating: 4.9624705 out of 5

Keywords: algorithms, algorithm, recurrence relation, substitution method, induction method, abdul bari, bari

Id: MhT7XmxhaCE

Length: 12min 24sec (744 seconds)

Published: Tue Jan 23 2018