Asymptotic Analysis (Solved Problem 1)

Asymptotic Analysis (Solved Problem 1)

Asymptotic Analysis (Solved Problem 1)

Data Structures: Solved Question on Asymptotic Analysis
Topics discussed:
1) Calculating the Time Complexity of the program with nested for loops.
2) Homework problem on calculating the time complexity.

C Programming Lectures: https://goo.gl/7Eh2SS

Follow Neso Academy on Instagram: @nesoacademy(https://bit.ly/2XP63OE)
Follow me on Instagram: @jaspreetedu(https://bit.ly/2YX26E5)

Contribute: http://www.nesoacademy.org/donate

Memberships: https://bit.ly/2U7YSPI

Books: http://www.nesoacademy.org/recommende…

Website ► http://www.nesoacademy.org/
Forum ► http://forum.nesoacademy.org/
Facebook ► https://goo.gl/Nt0PmB
Twitter ► https://twitter.com/nesoacademy

Music:
Axol x Alex Skrindo - You [NCS Release]

#DataStructuresByNeso #DataStructures #AsymptoticAnalysis #BigONotation


Content

0 -> Here in this presentation will consider us solved problem
2.64 -> one related to asymptotic analysis.
4.64 -> So, let's get started.
6.64 -> What is the time complexity of the following program?
9.52 -> The program is available in front of you.
11.52 -> You need to determine the time complexity of
13.94 -> this particular program. Here you can see, this is not
16.22 -> a complete program. Only a function is given in front of you.
19.02 -> And let me tell you that, this function accepts one argument,
22.12 -> that is value for n.
23.5 -> And within this function we have these statements written over here.
26.48 -> So, you can clearly see that the first statement is,
28.6 -> I'm declaring three variables and one more variable
31.12 -> and I have initialized this variable with value zero.
33.24 -> This is a count variable which is been initialized with value zero.
36.16 -> Then we have these for loops which are basically nested for loops.
39.3 -> And within this for loop have the statement, count plus plus.
42.42 -> You need to determine the time complexity of this program.
45.44 -> It would be better if you can pause the video
47.46 -> for a while and try to answer this question on their own.
49.92 -> I hope you're done.
50.8 -> Okay, let's move on to the solution.
52.36 -> Now, let's take this statement first.
54.36 -> Here you can see, I've declared three variables
57 -> and one more variable count which has been initialized to zero.
60.24 -> These three variables haven't been initialized.
62.42 -> We will use these three variables within these for loops.
65.38 -> You can see the time complexity in this case is big O of one because it's
68.64 -> just taking a constant amount of time for the execution.
71.24 -> You know, there are no for loops, nothing special.
73.68 -> You can treat this as a single statement.
75.68 -> Although, you can write these in multiple lines as well
78.4 -> but we treat this as a single statement.
80 -> If you treat them with different statements as well,
82.3 -> then also it will take constant amount of time.
84.3 -> Isn't that so?
85.28 -> So, this particular statement just taking a constant amount of time.
88.38 -> Now, let's consider this particular statement.
90.38 -> This is nothing but a for loop, right?
92.38 -> Within this for loop we have another for loop.
94.98 -> And within this for loop, we have another for loop.
97.38 -> Then we have this statement.
98.74 -> Obviously, our task is to find how many times
101.24 -> this particular statement has been executed.
103.24 -> So, let's first evaluate and try to understand
105.7 -> what this for loop is and how much time it will take.
109.08 -> In the iteration number one,
110.94 -> you can clearly see that i is equal to n by two. right?
113.56 -> You can write this as i equal to n by two plus zero.
117.28 -> Now, in the iteration number two,
119.28 -> it is clear that, this will be i equal to n divided by two plus one.
122.22 -> Because you can clearly see over here
124.1 -> that this is i plus plus.
125.42 -> An increment by one step.
127.22 -> So, obviously in the next iteration,
129.22 -> this will be n by two plus one.
131.22 -> In the iteration number three, this will be n by two plus two.
133.66 -> In the iteration number four, this will be n by two plus three and so on.
137.76 -> Now, let us assume that we are running upto
140.28 -> iteration number k, in that case i will be equal to
143.06 -> n by two plus k minus one.
145.3 -> Here you can clearly see in the iteration number one,
147.96 -> this value is zero.
149.08 -> Iteration number two, this value is one.
151.08 -> While this n by two remains constant,
153 -> only this value is changing with the iterations, right?
155.56 -> In the iteration number three, this will be two.
157.62 -> Iteration number four, this is three.
159.62 -> So similarly, in the iteration number k as well,
162.06 -> this will be k minus one.
163.72 -> So I will be n by two plus k minus one, which is equal to n.
168.04 -> Because this is the last iteration we are considering.
170.72 -> But we don't know how many times this has been executed.
173.26 -> That's why I have taken this as k.
174.66 -> So at this particular iteration,
176.36 -> i is equals to n by two plus k minus one, which is equal to n.
179.48 -> Now, let me rewrite this over here in a proper manner.
182.1 -> This is n by two plus k minus one equal to n.
185.58 -> Let's solve this.
186.66 -> We can write this k minus one equals to
188.66 -> n minus n by two without any problem.
191.24 -> I can bring this n by two over here.
193.24 -> By solving this, this becomes k minus one equal to
195.9 -> two n minus n divided by two.
197.9 -> Again, we can write this as k equals to n by two plus one.
200.94 -> This means that our loop is running n by two times.
204.82 -> I can take the least upper bound as n without any problem,
207.66 -> Loop executes n by two plus one,
209.74 -> which can be thought of as n by two times only.
212.6 -> Because plus one, if we won't consider, then it will not cause any problem.
215.96 -> We can take the least upper bound as n without any problem.
219.22 -> So this loop is actually running n times.
221.22 -> Although it is running n by two times,
223.14 -> let me tell you, but we are taking the least upper bound
225.24 -> without considering the constants.
227.24 -> So least upper bound of n by two is obviously n.
229.9 -> So we can say that this loop is running in times.
232.2 -> So this is big O of n.
234.2 -> Now, let's consider the next loop.
235.66 -> Here in this case, you have j equal to one
237.66 -> and this is quite interesting.
239.08 -> Here it is written j plus n divided by two less than or equal to n.
242.52 -> And here it is just j plus plus.
244.52 -> Let's see what is happening over here.
246.52 -> In the iteration number one, it is clear that
248.52 -> j is equal to one, right?
249.98 -> In the iteration number two, J is equal to two.
251.98 -> Iteration number three, j is equal to three.
253.98 -> Iteration number four, j is four and so on.
256.54 -> At iteration number k, j will be equal to k without any problem.
260.62 -> Because here in iteration number four, we have j equals to four.
263.34 -> Iteration number three, we have j equals to three.
265.34 -> So, it is clear that in iteration number k, j is equal to k
268.76 -> which is equal to n by two.
270.76 -> Why I am writing this as n by two?
273.14 -> j plus n by two less than or equal n
275.14 -> can be written as j less than or equal to n minus n by two.
278.38 -> I can bring this n by two over here.
280.38 -> This becomes n minus n by two.
282.38 -> I can solve this and this brings me n by two.
284.68 -> So, j is eventually less than or equal to n by two.
287.74 -> I can say that k is equal to n by two without any problem.
292.14 -> So it is clear from this fact that this loop is running n by two times.
295.88 -> I can take the upper bound as n
297.88 -> and can clearly say that loop is running
299.96 -> with the time complexity big O of n.
301.96 -> So, this is the upper bound I can take, which is n instead of n by two.
305.82 -> Always try to remove the constants.
307.82 -> Don't take n by two. Instead of n by two,
310.64 -> you can take a least upper bound that could be n.
313.08 -> Now let's see the other loop.
314.76 -> Here in this case, obviously we can
316.76 -> clearly understand that k is equal to one.
319.04 -> and k is less than or equal to n
320.78 -> and k is equal to k into two.
322.78 -> We have already calculated the time complexity
324.98 -> when these loops are available.
326.76 -> Here in the iteration number one, k is equal to one,
329.1 -> one can be written as two to the power zero,
331.04 -> two can be written as two to the power one.
332.82 -> Similarly, eight can be written as two to the power three and so on.
335.9 -> If I consider this up to iteration number p,
338.18 -> then this will be two to the power p minus one,
340.6 -> which is eventually equal to n.
342.6 -> Because in the last iteration, two to the power p minus one is n.
346.1 -> You can clearly see over here.
347.62 -> I can say that two to the power p minus one is equal to n
350.32 -> or n is equal to two the power p minus one without any problem.
353.48 -> I can take log on both sides.
355.06 -> This will become p minus one equal to log n base two.
358.32 -> I can write this as p equal to log n base two plus one,
361.3 -> which is equal to big O of log n.
363.3 -> I can eliminate this constant.
364.86 -> So, I can say that the time complexity for this loop is big O of log n.
368.88 -> Now let me tell you, these are nested for loops, right?
372.1 -> So obviously, you know that we need to multiply
374.26 -> these three time complexities.
375.86 -> n into n into log n, which is equal to big O of n square log n.
379.6 -> So, I can say that the time complexity for this particular code
382.74 -> is big O of n square log n or order of n square log n.
386.9 -> So, this is the time complexity of this particular code.
390.3 -> This loop is running n times.
392.3 -> I have taken the upper bound.
393.72 -> This loop is also running n times.
395.32 -> Again, I have taken the upper bound.
396.62 -> Here in this case, this loop runs log n times.
398.86 -> This is nested for loop structure. So here,
400.9 -> in this case we need to multiply these three time complexities.
403.8 -> n into n into log n will give us n square log n,
406.66 -> which is the final time complexity.
408.66 -> This statement is executing n square log n times.
411.3 -> So, this is the time complexity of this particular code.
415.3 -> Now, here is one homework problem for you.
417.3 -> The program is available in front of you.
419.3 -> Again, we have three nested for loops.
421.3 -> You need to determine the time complexity of this program.
424.08 -> And obviously, you can post your answers in the comment section below.
427.52 -> Okay friends, this is it for now.
429.52 -> Thank you for watching this presentation.

Source: https://www.youtube.com/watch?v=HFjJgSguqUA