1.5.2 Time Complexity Example #2

this I have this piece of code I have to analyze and find the time complexity of this one and this court also for loop is used but loop is starting from one going up to end that is less than n and it is being multiplied by two eyes multiplied by two every time so blindly we cannot say this will execute for n times we have to analyze this one let us see how many times this will execute it's not Emma we don't know how many times let us see I will take the I value initially this one the next time is going to be 1 e 2 2 that is true and this time it will be 2 into 2 again so it will be 2 squared see every time is getting onto that right - there is 2 square into 2 again so this will be 2 bar 3 goes on how many times that we don't know so let us say this will execute for 2 power K times 2 pi K times now we know that this will terminate when I becomes greater than equal to n so we assumed that when it has a reach for sub K number of times it has repeated assume I became greater than or equal to n and whatever I value 2 over K since I is equals to 2 power K therefore 2 power K has became greater than equal to now if I hate to part a is equals to n then K is how much log and base - yes this is the time complexity so the statement will execute for order of log n base 2 times so from this we can observe that if you have a loop where the counter variable it's not implementing but it's getting multiplied by something let us say 2 or 3 then it will get log base 2 time so you'll execute form operates two times now I have a implemented for the three at the regular loop that we use let us analyse that one and then we will analyze once again here the other method I will show you see here I is initially 1 and it is implemented by 1 plus 1 plus 1 n plus 1 goes on plus 1 and it will stop and finally it becomes greater than n so up to n so how many times is getting added so let us say K times and that is equal to n so how many times K times what is that K is equal to n now let's take this one I use initially 1 then it isn't it's trying to tell again into 2 then again into 2 so up to sometimes so finally it will stop when it becomes greater than equal to n then this is how many times so this will be let us say K time so what will be the result this will be 2 power K that will be equal to n so K is how much log in these two so the other we have analyzed this one so that is implementing 1 1 1 so kid I'm sorry d x - boo - every time so k times it's getting mighty tired so it's 2 per K that is equal to n so K is how many times games logon base to time so if you have any look like this the value of I is getting multiplied then it is going to take log and time so you can take it as a formula that I promised it click apply this algorithm as log and the statement will be forgotten times now you take log in log in me give decimal values float values so we need to know whether I have a have to take float or C log that value so that's important means should be truncated or round up the value so for that let us take some example and check it suppose n value is 8 right now I got him let us stop trace this one by taking a sample value is 1 initially then I have multiplied by 2 so it is 2 - miss less than 8 2 is less than 8 then I get x - 4 so 4 is less than 8 and is 8 right so again x true now it is not less than 8 so it will stop so total how many times it is repeating it is like waiting for three times the list if I take the N value and n if a rent of n value at 10 let us see what happens is initially 1 1 is less then 10 now n value is at 10 once less then 10 continued its multiplied by 2 so 2 is left then four four is less then 10 eight multiplied with it is 8 8 is also connected then 16 so 16 is I is not less than 10 so it will stop here so total how many times four times as executing four four times if I find log eight log interval between how long eight is written as two for three days and in the system as 3 log 2 base 2 and this is 1 so ancestry now save me if I find out the longer 10base2 now 10 is not in exact powers of 2 so I will not get the decimal valid integer value I'm gonna get a decimal value right so let us take it as an example 3.2 imagine audacity point to I what required you but if you see the number of times repeated four times so it should be taken as see the value so this log should be taken as seen when you use log sometimes whether it is seal or flow that is also important other piece of code here let us see how it's going to ask you what will return opposite of this one see here is starting from M a next time I values and bye to the mix timers n by 2 square then n by 2 cube so on how many times and by 2 for King we don't know the number of right should we are assuming it as for K times and we know that the loop will terminate when I becomes less than 1 so it will continue as long has a greater than equal to 1 so assume I have became less than 1 so therefore once I value 2 power K is less than 1 so if I equate it then is going to be 1 and n is equal to 2 power K so k is how much log n base 2 so again the time for this one is order of log and base 2 so the type of the city of this piece of course also without in this - so the previous one in the first example I have shown you that it was multiplying time and starting for a month now this is dividing every time starting from N and and up - what up - 1 it is reaching so it's part of login makes these fullest the 7th example and in here so here I started from zero and I need to add is less than equal to M so how many times the Select secured this is will execute as long as I is less than n but it will terminate when I into I is greater than equal to n we are seeing that ie twice I squared is equal to M so what is I is so 10 so I don't have to K here I am NOT Yusuke here that are ready using I only have shown you I advise the gentleman this is a square if you send that side it's a root so it will execute for root n times now the next example here I have 2 follows these are independent loops one after another don't mistake it as a nested loop they are not one inside another so the time complexity for this one is this is independent rule and it is situated for n times and it's incremental who sits order of N and this will also implement the loop this also order of n so if you combine them and take their time that is 2 plus 2 so n plus n that's true and and it is part of n so this is our independent group at the time is all rough and the only n plus n that is n it's not n square uh next one I have the easier independent loops this next loop I have to find out what is the time taken by the statement if I also only this one then J is taking rugs from one James less than J is implementing that is updating by x 2 every time so this is going to take a log value log of what love of people so this is log of P what is it be if you see the previous rule here be using demented so P is incremented in this group so this P will take the value that number of times this loop is repeating how many times the slope is repeating I get the runs 1 1 to N and I assign I introduce so again it's log log of what it is log n so P value will be log n and this statement will repeat for log P times so what is e he is evaluated here and it is used here right so this is log of love and as P is equal to log n so it is log of log n so the time complicities order of love next example here i have nested follow the outer loop is taking i assign 0 is less than n and eyes increment n so this is order of n as this is the increment loop so this order of n and whatever is they recite will repeat for and times next the in the follow this is using j j is less than n and j is every time x 2 right so this will take login time so this is a friend a login time and anything inside that also will take login time if remember initially I've shown you that this is mistakes n plus 1 no it will not be any useful if it I can don't write it makes no difference just you can take it as em now total homage to an organ plus n so hey Gaston is this one services or drove and log n so the type of the city of this one is order of n log n now let us write some pieces of code and see what the time complexities that we have got so far see if I write a for loop or I assign 0 I is less than n eyewitness for this for this figure that is order of n this link even a clue if this is written as by assign 0 I is less than n I I assign I plus 2 this is going to be n by 2 that also we take order of n then for any sign and I is greater than 1 I - - this also order of n so if it is incrementing also order friend if it is decrementing also order of n then for I assign 1 I less than then I assign I multiplied by 2 this is order of log n base 2 so it means before I assign one I use less them and I assign I in to 3 this will be order of log and base 3 4 I assign and I is greater than 1 and I assign I by 2 this order of log in base 2 so now we can take these as formulas if our loop is incrementing that is n or decrementing it is and whether it is in demanding by one hour two or even ten or even hundred also it's sort of Emily's same weight and my rules also order of N and by 200 is also order of because we are writing the degree of the polynomial that is n is the term used there the variable n is you said sort of an now sin square by 2 then the same square right so this is a summary of the time felicity we have seen

Channel: Abdul Bari

Views: 618,070

Rating: 4.9575944 out of 5

Keywords: Time Complexity, Algorithm

Id: 9SgLBjXqwd4

Length: 14min 12sec (852 seconds)

Published: Thu Jan 18 2018