1.5.3 Time Complexity of While and if #3

hi all the way I have prepared a video how to find the time complexity if there is a for-loop now the question is how to analyze a loop that is while loop or conditional statements see basically in C language there are three loops while and do-while there is a difference though while will execute minimum one time but follow fine while loop I say that they are same whatever you can do using for loop you can do using while loop and vice versa but before C language he has languages used to provide for loop in a different way let us see that follow for I assign one to M do some statements inside and this is : here this was the syntax in Pascal language now this loop says that I should take the values from 1 & 2 and write so always it will increase by one at a time all right so if you want to increase I by two times then you should say step two now I will be changing by two every time so I is 1 then it will become 3 then 5 and so on so it will take Y is 1 then 3 then 5 and so on but anyway I is incrementing linearly it is increasing all right so this was the only loops that were available in those days so that time follow and while loop very different then when you analyze this for loop already we have seen what is the time taken if I don't have this step steps let us say 1 only then this will execute time and this really good for n plus one time does the common thing and if you have while loop in this case then in a language if you have while loop then don't know what the condition is it will repeat as long as the condition is true and it will stop when the condition is false so we have to study this loop and find out when it is going to stop and how many times it is going to iterate based on that we have to do analysis and in this type of course interacts blindly for for loop means n no other time except n in this type of syntax and when the old languages were used so mostly in algorithms some books you will find this loop is use so it is an blindly and but while you cannot say and unless you studied thoroughly and in C language we have dou Y which is same as this while except that it will execute even if the condition is false it will execute for one time because it is post tested loop post check the loop first it will execute the statement inside then afterwards it will check the condition so if all the D condition is false in the beginning only it is false so this type will execute one time and this will not execute at all but in old languages they used to be a loop called repeat some statement inside and under some condition now these loops were different repeat until loops are different this will repeat as long as a condition is false and once the condition is true it will stop so it is similar to do while how minimum one time the statement is but it is different compared to Dubai how do while we'll execute as long as condition is true repeat until we'll execute as long as condition is false it will stop when the become condition becomes true do this until this happens so if it happens you have to stop so if you take English sentence statement repeat until this happens so if it happens you have to stop if it is not happening you have to go on continuing so that's the difference between them now all these three loops all these three loops you have to study them then only you can give the time complexity their time complexity can be n log N or oten it can be anything but for loop we can directly say it's order of n now let me write few pieces of code or snippets where I will use while loop I have written a piece of code using by loop I have to analyze how many times this will execute what is the time complexity of this one I want to know how many times this statement will execute initially I is zero this will take one unit of time an I plus plus how many times this will repeat how many times this will repeat see I plus plus it is just incrementing every time so simply without tracing this one I can say that this will repeat for n times how many times this statement will execute again n times only how many times this will execute n plus one time how n times the condition will be true and one time the condition is false so if for example n is a ten then this is going to repeat for total ten times zero to ten it will stop and I become stem and how long this will execute as long as I is from zero to nine so this n time right and that is one extra then what is the time taken by this piece of code three and plus two is three and plus - so the function f of n s 3 and +2 and it is teed off and now order of n now the same piece of code in C language I can write like this for I assign 0 here then I is less than n I is less than n I plus plus I plus plus no what is the analysis for this fund it will be saying if I consider each and everything this is execute for one time this will execute for n plus one time this will execute for n time and this will execute for n time total how many 3 n plus 2 but when I was using for loop I was saying that let us ignore these two and just take it as n plus 1 so I was saying that it was 2 n plus 1 whatever the function may be we are not interested in exact formula or exact function we are interested in the degree of a function so we say order of n now that's it now you can see whatever I can write using while loop I can write it using for loop also now our next piece of code here see a assign 1 while a is less than B some statement and a is multiplied by 2 every time there is no n here then how many times it was repeat I don't know this depends on this condition as long as the condition is true it will continue so I don't know how many times it's going to run let us trace this one is initially 1 right the name is becoming a into 2 so that is 1 into 2 so it is becoming to the next time again this is 2 so 2 into 2 again so this will become 2 square the next time again this is 2 square into 2 that is 2 q goes on how many times this is going to happen I don't know let us assume that somewhere it stops and at that time this is going to be two parking so it will repeat four K times and that's what K I have to find out I don't know how many times so I am say King K times now I say that it has stopped here so you should know when it is stopping it will terminate when is greater than or equal to B it will terminate when a is greater than equal to B so what I am saying I has reached till 2 power K so since I am saying that a is equal to 2 power K now so this is 2 power K is greater than equal to B let us make it equal 2 power K is equals to B so what is K log being base 2 so how many time is going to execute log B Times log B Times log B times rewrite the time complexity in the form of log n NV u storm n what have you got the answer in B so let us call B itself as n so what is the time taken by this algorithm it is order of log n that's it this is how I can analyze already I have shown this using for loop that time I was writing the same thing by using for loop like this for a assign 1 is less than B a assign a into 2 this portion is here that's all already we have seen this in follow ups I have shown you this one already we know this one that time I was not taking a I will take ie and again here also I and this I will call it as n and this I will call it I that's it basically this is not proper based on full loop because formants it should just go on incrementing or it should be decrementing it should not multiply I but in case of C language it is possible you write anything has initialization any condition you write anything as updation so these three pieces you can write whatever you like just make sure that the loop terminates after some finite number of steps so that's all what all you can do using while loop you can also do it using for loop in C language and the examples what I have given in all the examples I have used for loop only but in so for loop just you can reframe them as while loop let us take one more example again a loop is there while loop and in this while loop I is starting from N and I is dickweed getting divided by two every time so again the time will be log and I made it as a formula already in the previous video so this will be log N and the same thing can also be done using for loop for I assign n I is greater than 1 I assign I by 2 some statement inside so this type of statement already we have analyzed and for loop that same thing is using while loop so the time will be seen now here I have a loop let us see how many times this will execute condition is K is less than n and here what is K K is 1 and K is getting updated by adding ie every time and I use incrementing every time so I don't know how many times it's going to execute so let us take trays this one I and K initially both are 1 so 1 is less than n we don't know what n is and what happens k assign k plus I so this becomes 1 plus 1 that is 2 and I plus plus I becomes 2 now as you in case - 2 is less than n the next K assign K + I so 2 + 2 right and I becomes 3 the next time again K let us say it is less than I so then K assign K + I so this is 2 + 2 + 3 + I becomes 4 next time it will be 2 + 2 + 3 + 4 + I becomes 5 so this is going on continuing so how many times I don't know how many times let us call it as 4 M times K already I am using it here so 2 + 2 + 3 + 4 + goes on to M if I make this as 1 then you can see that is some off and natural numbers so this will be M into M plus 1 by 2 roughly plus 1 it's strong roughly it is this much now this is K value will be this much bit it has gone till M and K value this much and let us assume it has dropped so what is the condition K is less than n it will continue when K becomes greater than n or equal to n it will stop so I assume that K became greater than or equal to n so what is K I am saying I have stopped K at M into n plus 1 by 2 that is greater than equal to n this is roughly equal to what M square is greater than n so M is what root n approximately at this root n so it will repeat for M times so what is M root and so the time complexity of this one is order of root n same thing I can write using for loop also for K assign 1 comma I assign to initializations condition is what K less than n updation is what I plus plus and one more updation is there that I will do inside the statement and K assign k plus I there's the same thing how long this is executing route and how long route and again one two one two condition condition updation updation the submission in the submission everything is as it is so what i wrote using vial can also be written using for this is little difficult to read that is clear and easy to understand all right so already we have seen this type of loop now I have written it using while loop next this piece of code is for finding GCD of two numbers m and n now how many times it will repeat this will repeat for some time until MN n becomes equal it will be repeating when they become equal it will stop so when they are equal so that is a GCD value either you say M or you say n how many times it will execute I don't know so let me trace if M is equals to 6 and n is equals to 3 initially then what happens n is greater than n yes so M minus n so this becomes 6 minus 3 that is 3 and is also 3 this one now they became equal so it has executed only one time if I take M and n both are 5 5 then how many times they are equal it will not enter inside so it will execute 0 times so it is minimum executing 0 or 1 times let's say m is 16 and n is 2 now how many times this will execute MN n are not equal M is greater than n year 16 is greater than to enter inside Emma sign and minus n so M becomes how much 14 and this will be to only now hanging in M is greater than n only so again 2 is subtracted so this becomes 2l and this is true only again 12 is greater than 2 so this becomes 10 and this is true only and this becomes 8 + 2 6 + 2 4 2 2 2 nor it will stop now the both became equal so it will stop how many times it has executed 1 2 3 4 5 6 7 7 times so almost 16 by 2 times so it means it will execute for n by 2 times so I can say it is order of n so the maximum time taken by this algorithm is order of N and what is the minimum time taken by this algorithm it is 1 means 1 time it is executing so minimum time is order of 1 maximum time is order of n I can write the same thing even using for loop I'll just convert it into for loop for nothing initialized and only the condition then no objection I can use for loop also anyway this is the GCD one of the procedure there are other procedures also you can find out that and in this procedure at the time I am getting it as n by 2 so I wrote it as order of n so if it is a while loop then I have to study it and find out now same thing in C language can also be done using for loop so even it is for loop in C language you must read as while only and study it unless and until it is obviously order of M you have to study it yes I am taking one example here which will show what happens if is there just a random code I have written here this is not meaningful it's not doing anything algorithm test is taking some parameter and if n is less than 5 just print n if n this greater than or equal to 5 then enter in the else part and repeat this loop so how many times this loop is going to execute this will execute for n times and what about this this will execute for one time that's it if algorithm is using some conditional statements then the conditional statements may decide different amount of time in depending on the condition if the condition is true then it's going to execute just one statement so the time is order of one and if the condition is false means is greater than five then is going into repeat for n times so it is part of n so this is best case time and this is worst case time so I can say that if there are so I can say that if there is a conditional statement in an algorithm then it can decide or give different amount of time depending on the condition so may be it may become those case or best case or of an algorithm it's not necessary it's not necessary it means it doesn't mean that if if is there is not a little formula or rule if it's there then definitely it will take that much time it's not necessary now I think I will make some change here G in the condition now now this will execute for n times N greater than 5 right now there is no minimum or maximum there is no best case or worst case if n is greater than 5 it will execute that's all so as I said that you cannot take it as a rule that if conditional statement if s there the time will be different all right so that's all about the loop and the conditional statements while loop and the conditional statements this is how they have analyzed

Channel: Abdul Bari

Views: 450,282

Rating: 4.9505019 out of 5

Keywords: algorithms, algorithm, time complexity, loop time complexity, while loop complexity, while loop time, abdul bari, bari, gate

Id: p1EnSvS3urU

Length: 21min 53sec (1313 seconds)

Published: Thu Feb 01 2018