YT YouTube2Text

YouTube2Text → Transcripts → Understanding the Time Complexity of an Algorithm

Understanding the Time Complexity of an Algorithm — Transcript

by Neso Academy · 3,175 words · 475 segments · language en · Watch on YouTube

Open in transcriber Summarize with AI Download SRT/VTT

Full transcript

0:01[Music]
0:06we are done with the chapter of
0:08asymptotic notations where we discussed
0:11different types of asymptotic notations
0:14and the problems based on it now from
0:18this lecture onwards we are starting a
0:20new chapter where we will discuss how to
0:24find the time complexity and the space
0:27complexity of algorithms involving
0:30Loops in this lecture we will first
0:34understand the time complexity in great
0:37details and then through an example we
0:40will understand how to analyze the time
0:43complexity of an algorithm in involving
0:46Loops so let's get started with this
0:49lecture and let's see what are the
0:52topics the first topic of this lecture
0:55is priori versus posterior analysis
0:59recap we will first get the quick recap
1:02of priori and posterior
1:05analysis and then we will understand CPU
1:08computations and Main memory space we
1:11will understand these two terms in great
1:14depth and then we will understand the
1:17time complexity and finally through an
1:20example we will understand how to
1:23analyze an algorithm and that to an
1:26algorithm which involves Loops so let's
1:29get started and let's get the quick
1:31recap of the priori versus posteriori
1:36analysis we know the difference between
1:38priori and posterior analysis from our
1:42previous
1:43chapters let's get the quick recap of
1:46priori and posterior
1:48analysis in case of priori analysis we
1:52estimate time and memory space required
1:56by an algorithm before executing it on
2:00the system but in case of posterior
2:03analysis we calculate time and memory
2:07space required by an algorithm after
2:11executing it on the
2:13system here in case of priori analysis
2:17we estimate time and memory space this
2:19means we do not calculate the actual
2:22time and memory space required by an
2:25algorithm and we estimate time and
2:27memory space before exit executing our
2:30algorithm on the
2:32system so before executing the algorithm
2:36we estimate time and memory space it
2:39takes in case of posterior analysis we
2:43calculate the actual time and memory
2:46space required by an algorithm after
2:48executing it on the system so
2:51posteriority analysis depends upon the
2:54system priori analysis does not depend
2:57upon the system because we are analyzing
3:00the time and memory space required by an
3:03algorithm before executing it on the
3:06system in case of priori analysis our
3:10focus is on priori analysis because
3:13priori analysis is the easiest and it is
3:16the most practical
3:18analysis so keeping this in mind we will
3:21use priori analysis to analyze our
3:24algorithms now how do we estimate time
3:27and memory space is the main question
3:31the estimation of time is same as the
3:34estimation of total number of CPU
3:38computations an algorithm takes and
3:41estimation of memory space means
3:45estimation of main memory
3:47space we will understand how do we
3:50estimate main memory space later but in
3:53this lecture we will understand how to
3:56estimate time or in other words how to
3:59estimate
4:00the total number of CPU computations an
4:03algorithm needs to
4:06execute now what is the meaning of CPU
4:10computations let's understand the
4:12meaning of CPU computations and Main
4:15memory space first after this we will
4:18learn how to analyze an algorithm or in
4:21other words how to estimate time and
4:24memory space required by an algorithm so
4:28now we will understand the meaning of
4:32CPU computations and Main memory
4:36space so what is the meaning of CPU
4:40computation a CPU computation refers to
4:43a task performed by the CPU or
4:47instruction executed by the CPU so CPU
4:51computation refers to a task which is
4:55performed by the CPU at any point of
4:58time or it refers to an instruction
5:01executed by the CPU in simpler terms so
5:05the meaning of CPU computation is an
5:08instruction executed by the CPU now what
5:12is the meaning of main memory space main
5:16memory space is used to temporarily
5:19store data and instructions that CPU
5:22needs for quick access during program
5:27execution one thing is clear that our
5:30focus is on CPU or Central Processing
5:33Unit whenever a CPU performs a task we
5:37call it a CPU computation or we can say
5:40whenever an instruction is executed by
5:43the CPU we call it a CPU
5:46computation and we are focusing on the
5:49main memory space because main memory or
5:52random access memory which we also call
5:54RAM is required by the CPU for quick
5:59access of the data and instructions
6:02stored in it main memory space is of
6:06concern to us and we are also concerned
6:09with the total number of CPU
6:12computations required by an algorithm so
6:15these are the two terms which I hope are
6:18completely clear to you the meaning of
6:21CPU computation is an instruction
6:23executed by the CPU and Main memory
6:26space is the memory space required by
6:29the CPU for quick access of data and
6:33instructions during program
6:36execution now as we have understood the
6:39meaning of CPU computations and Main
6:41memory space we are in the state to
6:45understand the time
6:47complexity so what is time
6:50complexity time complexity refers to the
6:55estimation of total CPU
6:58computations record IR ired to execute
7:01an algorithm we just understood the
7:04meaning of CPU
7:05computations we are not bothering about
7:08main memory space at this moment later
7:11we will understand how to estimate main
7:14memory space but right now our focus is
7:17to understand the time complexity and
7:20time complexity is the estimation of
7:24total CPU computations required to
7:27execute an algorithm now the main
7:30question is how do we estimate total CPU
7:35computations we now know time complexity
7:38of an algorithm is equal to total number
7:42of CPU computations but the question is
7:45how do we know the total number of CPU
7:47computations of an
7:50algorithm we can calculate the total
7:53number of CPU computations by using the
7:56method which we call the frequ quency
8:00count
8:01method according to this method we
8:04calculate the sum of frequency count of
8:08each instruction of an
8:11algorithm so frequency count method is
8:14the method in which we calculate the sum
8:17of frequency count of each instruction
8:20of an
8:21algorithm so total number of CPU
8:24computations is equal to the sum of
8:27frequency count of each instruction of
8:31an algorithm now what is the meaning of
8:33frequency count frequency count refers
8:37to the number of times an instruction is
8:41executed so in order to calculate the
8:44time complexity of an algorithm we
8:47calculate the sum of frequency count of
8:50each instruction of an algorithm and
8:53frequency count refers to the number of
8:56times an instruction is executed so by
9:00seeing an algorithm you can calculate
9:02its time
9:04complexity and now we will understand
9:07how to do this so now we're going to
9:10take a simple example algorithm and
9:14through that algorithm we will
9:16understand how to calculate the time
9:20complexity and that to using the
9:22frequency count method so now let's move
9:26to the next topic where we will consider
9:28a simple example algorithm to understand
9:32the time complexity
9:34properly here is the example algorithm
9:38here I have written the algorithm in C
9:41like syntax because C like syntax is
9:44simpler to understand and many students
9:47might already know C programming
9:50language so it is my assumption that you
9:52are familiar with at least one
9:54programming language if not C if you
9:57know C programming language AG then it
10:00is great but if you don't know C
10:02programming language you can still
10:04follow along there is no
10:07issue this algorithm is written in C
10:10like syntax and I've mentioned algo here
10:14to indicate that this is not a c program
10:18this is an algorithm this algorithm is
10:23non-executable this algorithm is written
10:25for us to understand how to analyze the
10:28time
10:30complexity so now we are going to
10:32analyze the time complexity of this
10:35algorithm using the formula which we
10:37just saw we are going to use the
10:40frequency count method to calculate the
10:43time complexity of this algorithm so we
10:46will do the priori analysis of this
10:49algorithm this means we will estimate
10:52the time complexity of this algorithm
10:55through the frequency count method now
10:57let's proceed and let's do this the job
11:00of this algorithm is to calculate the
11:02sum of N elements of the list
11:06a so n represents number of elements and
11:11a represents list of n
11:14elements here in this algorithm the
11:17first instruction is sum equal to0 this
11:22instruction tells CPU to assign zero to
11:25variable sum here only one operation is
11:29per formed hence this is just a single
11:31instruction and this instruction is
11:34executed only once so the frequency
11:38count of this instruction is
11:40one now why is that the case we know the
11:44meaning of frequency count frequency
11:46count refers to the number of times an
11:50instruction is
11:52executed this instruction is executed
11:56once here we have just one assignment
11:59that's it only one operation and it is
12:03executed only once therefore the
12:05frequency count of this instruction is
12:08one and let's assume that one
12:11instruction takes one unit of time
12:14therefore this instruction takes one
12:17unit of time now if you want to know the
12:20time complexity of this algorithm we
12:23need to calculate the sum of frequency
12:25count of each instruction in this
12:28algorithm
12:29so let's put one here here we will
12:32calculate the sum of frequency count of
12:35each instruction the frequency count of
12:38this instruction is one and this is the
12:41reason why I have written one here now
12:44what is the next
12:45instruction this is the for Loop and I
12:49hope you already know the meaning of for
12:51Loop for Loop allows us to execute
12:55instructions a certain number of times
12:59this Loop will allow us to execute this
13:03instruction which is part of the for
13:05Loop a certain number of
13:08times in this for Loop we have this
13:11instruction I equal to
13:131 this is an assignment instruction and
13:18this instruction will be executed only
13:21once because this represents the
13:24initialization of I so clearly the
13:28frequency count of I = 1 is 1 and
13:33therefore the time it takes is 1 unit
13:38and hence one can be added in this sum
13:42now what's the next instruction the next
13:44instruction is I less than or equal to
13:48n what can we say about this instruction
13:51what is the frequency count of this
13:55instruction I want you to pause this
13:57video and I want you think about this
14:00what is the frequency count of this
14:04instruction so pause the video
14:08now I hope you're done okay so what's
14:12the Frequency count of this instruction
14:15the frequency count of this instruction
14:18is n + 1 and hence it will take n+ 1
14:23units of time now why is this the case
14:27you might have given the answer as n and
14:31you are quite close but n is not the
14:34correct
14:36answer n + 1 is the correct answer why
14:41let's find out we know here we are
14:44checking a condition we are checking is
14:47I less than or equal to n if it is the
14:50case that I is less than or equal to n
14:54then this statement sum equal to sum +
14:57AI will be exec Ute
14:59it then I is incremented and the
15:03condition is checked once again so we
15:05know the initial value of I I is 1 one
15:09is compared with n this is the first
15:12condition checking first we are checking
15:15is 1 less than or equal to n if true we
15:18will get inside and execute the
15:21statement then I is incremented I
15:23becomes 2 then we will check this
15:26condition once again is 2 less than or
15:29equal to n this is the second condition
15:32check then we will go inside execute the
15:35statement I is again incremented it
15:38becomes three then three is compared
15:41with n this is the third time the
15:44condition is
15:46checked and this will continue and then
15:49we will compare n with n eventually I
15:52becomes n and we will compare n with n
15:56but we know n is equal to it is not less
16:00than n still the condition is true and
16:04hence the statement inside the for Loop
16:07that is Su equal to Su plus a I will be
16:10executed and I is incremented by one we
16:14know I is n and n ++ is equal to n + 1
16:19so the next condition check is n + 1
16:23less than or equal to
16:24n can we say n + 1 is less than or equal
16:28to n
16:29no right n + 1 is not less than or equal
16:34to n it is greater than n therefore at
16:38this point this condition becomes false
16:41hence we will go outside this
16:44Loop we are done with this loop at this
16:48point how many times this instruction is
16:51executed a total of n + 1
16:55times therefore there are n + 1
16:59comparisons and hence we can say the
17:02frequency count of this instruction is n
17:05+ 1 and this is the reason why this
17:09instruction will take n + 1 units of
17:13time so now we can add n + one here I
17:17hope this point is clear now what can we
17:21say about this instruction
17:23i++ how many times do you think this
17:26instruction will execute
17:29let's try to understand this now this
17:32instruction will execute based on this
17:36condition if this condition is satisfied
17:39this means if this condition is true
17:42then this instruction will execute if
17:45this condition is false then this
17:47instruction will not execute why am I
17:50saying this let's now try to understand
17:53this the initial value of I is 1 let's
17:56say 1 is less than n this condition is
17:59true if this condition is true we will
18:02go inside the for Loop and execute the
18:05statement after execution of the
18:08statement I ++ will execute so it is
18:12clear when this condition is satisfied
18:16i++ will
18:17execute but what when this condition
18:20becomes false if this condition is false
18:24then this statement sum equal to sum
18:26plus AI will not execute and hence this
18:30instruction will also not execute
18:33because i++ can only execute after
18:37execution of the
18:39statement so one thing is clear that
18:42when this condition is true I ++ will
18:45execute if this condition is false then
18:48i++ will not
18:50execute now let's use this idea to
18:54understand how many times this
18:56instruction will execute the initial
18:59value of I is 1 and I'm assuming 1 is
19:02less than n therefore the condition is
19:05true after execution of the statement I
19:08is incremented by 1 this means I ++ is
19:13executed for I =
19:161 after execution of this instruction I
19:20becomes 2 after I becomes 2 this
19:24condition will again
19:25checked let's say 2 is also less than n
19:29the condition is once again satisfied as
19:32this condition is satisfied I ++ will
19:35definitely execute so for I equal to 2
19:40also this instruction will
19:43execute what about I = to 3 let's say
19:46for I equal to 3 also this condition is
19:48true then it is surely the case that I
19:52++ will execute and hence for I = 3 also
19:56I ++ will execute
19:59similarly for i = 4 also this
20:02instruction will execute again assuming
20:05the same thing that 4 is less than n now
20:08let's say this process continues up to I
20:11= to n when I becomes n then n is
20:17compared with n as this condition is
20:20satisfied I ++ will again execute
20:24therefore for I = 1 to n this in
20:28instruction will definitely execute
20:31after I equal to n this instruction will
20:34execute and hence I becomes n + 1 we
20:37know that this condition will be checked
20:40once again for I = to n + 1 but this
20:44time this condition is not satisfied
20:46because n + 1 is neither less than n nor
20:49it is equal to n as we know the
20:53condition is not satisfied therefore I
20:56++ will not execute this time so for i =
21:00n + 1 this instruction will not execute
21:04only for i = 1 up to n this instruction
21:10will
21:10execute and this clearly shows that i++
21:14will execute n times not n + 1 times
21:20hence the frequency count of this
21:22instruction is n and the amount of time
21:25this instruction will take is n n
21:29units so now we got to know that this
21:33instruction will take n units of time so
21:37now we can add in here for this
21:41instruction now what about this
21:43statement sum equal to sum plus
21:46AI this is one statement but in this
21:50statement we have a total of two
21:53instructions here we are performing the
21:55addition operation and we are also
21:58assigning the result of sum plus AI to
22:02sum so there are a total of two
22:05instructions now how many times do you
22:08think this statement will
22:10execute this entire statement will
22:12execute n times because of the same
22:15reason which we saw in case of I
22:19++ the execution of this statement also
22:22depends upon this
22:24condition hence when this condition is
22:28true then this statement will execute
22:30when this condition is false then this
22:32statement will not execute so it is
22:35clear the number of times this statement
22:37will execute is also
22:40n but here we have a total of two
22:43instructions therefore the total time
22:46required to execute the statement is 2N
22:51units the frequency count of the
22:53statement is 2
22:55N so now we can add 2 N here here as
22:59well now what can we say about this
23:01statement return sum this is just one
23:05instruction and hence it will take one
23:07unit of time so we can add one here for
23:11this
23:12instruction now here we can calculate
23:15the total frequency count of this
23:19algorithm this is equal to 4n + 4
23:23because 2 n + n + n is equal to 4N
23:281 + 1 + 1 + 1 is equal to 4 so we got 4
23:33n + 4 as 4 n is the dominating term
23:38therefore big of n is the time
23:42complexity of this
23:45algorithm we can use different notations
23:47here to represent the time complexity
23:51but I'm using the biger notation which
23:53is also correct so the time required to
23:56solve this algorithm is Big of n which
24:00is the linear time as the size of the
24:04input grows the time required to solve
24:07this algorithm grows
24:10linearly it is Big go of
24:13n now we know what is the time
24:15complexity of this algorithm and we got
24:18to know this by knowing the frequency
24:21count of each instruction of the
24:23algorithm in this way we can calculate
24:26the time complexity of any algorithm so
24:30I hope the idea is completely clear with
24:33this we are done with all the topics of
24:36this lecture and hence we are done with
24:38this
24:39lecture okay friends this is it for now
24:42thank you for watching this presentation
24:44I will see you in the next one
24:47[Applause]
24:50[Music]

About this transcript

This page contains the full transcript of Understanding the Time Complexity of an Algorithm by Neso Academy, generated from the public captions YouTube serves with the video. The transcript has 3,175 words across 475 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.