YT YouTube2Text

YouTube2Text → Transcripts → 1.5.3 Time Complexity of While and if #3

1.5.3 Time Complexity of While and if #3 — Transcript

by Abdul Bari · 3,188 words · 391 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

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

About this transcript

This page contains the full transcript of 1.5.3 Time Complexity of While and if #3 by Abdul Bari, generated from the public captions YouTube serves with the video. The transcript has 3,188 words across 391 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.

What you can do with it

Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to translate the transcript into 100+ languages.

Free YouTube transcript tool

YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, translation to 100+ languages, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.