How to Calculate Time Complexity of an Algorithm + Solved Questions (With Notes)
How to Calculate Time Complexity of an Algorithm + Solved Questions (With Notes)
Learn how to calculate time complexity (Big O) of a program in hindi. these Data Structures and algorithm videos will walk you through the series of topics you need to learn to prepare for a placement interview
➡Join this DS \u0026 Algo course \u0026 Access the playlist: • Data Structures and Algorithms Course…
➡Download Source Code \u0026 Notes here: https://codewithharry.com/videos/data…
►Checkout my English channel here: / programmingwithharry
►Click here to subscribe - / @codewithharry
Best Hindi Videos For Learning Programming:
►Learn Python In One Video - • Python Tutorial In Hindi 🔥
►Python Complete Course In Hindi - • Python Tutorials For Absolute Beginne…
►C Language Complete Course In Hindi -
• C Language Tutorials In Hindi
►JavaScript Complete Course In Hindi -
• JavaScript Tutorials In Hindi
►Learn JavaScript in One Video - • JavaScript Tutorial
►Learn PHP In One Video - • Learn Php In One Video In Hindi - हिं…
►Django Complete Course In Hindi -
• Python Django Tutorials In Hindi
►Machine Learning Using Python - • Machine Learning Tutorials For Beginn…
►Creating \u0026 Hosting A Website (Tech Blog) Using Python - • [Hindi] Web Development Using Flask a…
►Advanced Python Tutorials - • Intermediate/Advanced python Tutorial…
►Object Oriented Programming In Python - • Object Oriented Programming Tutorials…
►Python Data Science and Big Data Tutorials - • Python Data Science and Big Data Tuto…
Follow Me On Social Media
►Website (created using Flask) - http://www.codewithharry.com
►Facebook - / codewithharry
►Instagram - / codewithharry
►Personal Facebook A/c - / geekyharis
Twitter - / haris_is_here
Content
0 -> Before Solving Some Questions of Time Complexity
2.84 -> I will tell you some tricks to get rid of time complexity.
6.626 -> after that we will do some set of questions.
8.357 -> which will make you a very good grasp in such questions.
12.474 -> due to the time complexity.
13.564 -> So here first of all i will talk about
15.926 -> the time complexity of any algorithm when you have to find it
19.826 -> so what is the first step that you do
22.327 -> and at the same time how to approach this problem,
25.636 -> That I am going to tell you people.
27.145 -> So here first of all I would like to talk about what is that reason
31.68 -> And quickly we will talk about the basics
33.498 -> as we have already talked about it:
35.05 -> If you haven't accessed the playlist,
36.896 -> be sure to check the data structures and algorithms.
40.231 -> So here what i will do, i will write the tricks and
43.529 -> write the first technique, I will not waste much time
46.542 -> The first technique to find out the time complexity is:
50.872 -> that you drop the non-dominant terms, okay.
54.481 -> Drop the non-dominant terms
60.568 -> You drop whatever non-dominant terms you have
65.707 -> What does this mean
66.662 -> suppose you are given a for loop
70.372 -> OK, I'm writing a for loop: a simple for loop.
73.083 -> for(i=0; i
76.621 -> This is your (n) times running for loop:
79.19 -> It is written in (c) language
80.797 -> And above I have also written (n) time, let's assume
82.892 -> (i=0; i
85.643 -> Now this for loop is doing some work
88.723 -> So first of all what you people have to do,
92.192 -> whatever problem you are given to people
94.365 -> you have to break it into fragments.
96.826 -> And in one fragment you get some time
100.001 -> Suppose here is happening (int), (int) not inside the for loop
105.107 -> (k=i) is happening over here,
108.025 -> something (k) will happen above
109.002 -> And I'm just trying to make a sample program here
112.696 -> And the same thing is happening here (k++), let's say
117.597 -> that's just happening, anything else is happening!!
119.835 -> Let's say (x=y+1) is happening
122.618 -> and it's going on inside the loop.
124.583 -> So what will happen that this thing:? Does it dependent on (n),
130.005 -> It does not dependent on (n)
131.615 -> So let's do it, whatever work is going on inside the for loop.
137.649 -> it will be the same every time, because it's not depending on (n)
140.942 -> Now the value of (i) is increasing,
142.887 -> but let us assume that the portion here is, (k) is taking time.
146.643 -> Suppose it takes (k) time to run
150.166 -> which are the statements inside it
152.365 -> How many times are these statements being run?
154.665 -> It is running (n) times, because this loop is running (n) times
158.086 -> Okay.
158.586 -> So what will be the time!, If I get time for the algorithm, then
162.076 -> then it will be (k*n), okay.
164.984 -> So it will be (k*n)
167.058 -> Now here it will not be equal to Exact (k*n),
170.942 -> but will be very close to (k*n)
173.382 -> Why wouldn't exactly be equal?
175.472 -> Because when the value of this (I) increases,
177.624 -> it will make a difference in some time.
179.361 -> So we ignore that thing
181.171 -> We're here to assume that that's all the steps.
184.551 -> k=i, k++ and x=y+1
188.24 -> In this way, whatever instructions are going on here,
192.798 -> it is taking almost (k) time, on and average
195.682 -> (k) will be same either above or below
197.945 -> So that's why we took it as a constant (k)
199.451 -> Now the time taken to add 1 to 2,
202.303 -> and add 2 to 4 when you hit the exact time,
205.422 -> would be the time it took to add 2 to 4
207.651 -> will be different when 1 to 2 is added to its time.
211.225 -> But we ignore that,
211.95 -> We believe that these operations are all (k) time consuming
215.056 -> This for loop, that is,
216.665 -> how much time is being taken for this fragment
219.846 -> It seems (kn), okay
221.591 -> So before this (int i) would have been written here,
224.238 -> (int k=0) would have been written
226.139 -> I'm just guessing, there will be some code above, ok
228.55 -> And that code has nothing to do with (n)
231.8 -> So what will I do, I will write here (k1),
235.18 -> as if he is taking time (k1)
236.361 -> I take this for (k2) here, I accept this (k1)
240.413 -> So I will say (k1+k2n) or (k2n+k1) it is taking time
244.239 -> to run my entire code.
246.79 -> ok, this whole code has to be run
249.195 -> Now see what will happen here,
250.529 -> this whole code is taking (k1+k2n) time to run
254.837 -> What I said here were drop the non-dominant terms
257.476 -> When I talk about time complexity
261.387 -> I believe that whatever (n) happens, will be huge.
265.073 -> because a sufficient, sufficiently high value of (n) is taking
268.66 -> I told you in the definition of big O
270.585 -> (n=n0) is quite high:
274.316 -> So we do Time Complexity Analysis for huge value.
278.76 -> when the value of (n) will become very high
280.131 -> When the value of (n) becomes very high,
281.669 -> then out of (k1) and (k2n),
284.372 -> (k2n) which is the larger number will be
286.719 -> So we won't compare these two, and we'll drop it
289.898 -> We will say that (k1),
291.524 -> when (n) is really very high in front of (k2n),
294.443 -> then he will not be able to stand
295.952 -> And (k2n) it will be time, okay
297.901 -> So far I have only applied (k2n)
300.123 -> After that there is a second role to preciously describe big O.
304.514 -> Drop the constant
305.907 -> Drop the constant term
310.743 -> Okay
311.243 -> Drop the constant term
312.285 -> Now what will happen here, I will remove the constant term
315.18 -> then it will be O(n)
317.099 -> So once the for loop is running over here,
319.509 -> and that (n) running times,
321.85 -> (i) is running for n-values, O(n)
324.511 -> Because as I keep growing (n), this work will happen so many times more
328.176 -> if (n) is 3 here, then this loop will run 3 times then (k2*3)
332.408 -> Similarly, if (n) times will run then (k2*n)
335.09 -> and here I have O(n) found it.
337.542 -> found O(n), Okay
339.169 -> Drop the constant term
340.791 -> The third technique that I want to tell you is this:
344.084 -> That break the code into fragments
346.743 -> Okay
347.611 -> Break the code into fragments
352.332 -> i'll give you an example
354.429 -> Fragments
356.203 -> and why we broke in fragments?
358.458 -> See, let's say a loop is going on
360.629 -> and let's say another similar loop is going on
363.896 -> Which will work for (i = 0(n)),
367.342 -> I rub it a bit, okay
370.298 -> i rub it
372.149 -> Suppose this code is not ending here
374.46 -> and another for loop in this code:
376.873 -> it's something like that, for(j=0; j
383.431 -> A lot of people who make mistakes know what they do
385.948 -> Let it have (k=i+1)
387.727 -> or suppose there's (k--), okay
391.463 -> What many people who make mistakes will they do,
393.51 -> (n) look here, (n) look here
395.183 -> and will say it's (n²)
396.659 -> and it isn't (n²)
397.531 -> And why it is not, how to know, what is it, I will tell you
400.898 -> Look at the work being done on it, it is as if it is a complete code file.
404.299 -> I have to find the snippet time of this algorithm
406.707 -> first i will break it into fragments
408.94 -> The first fragment turned out to be this one,
410.859 -> with a little bit of initialization
412.205 -> It took constant time,
413.993 -> because it is not such that if the value of (n) increases,
416.364 -> then its time will increases.
417.511 -> (nth) Time is going to be (nth) Time, isn't it?
419.236 -> even if I walk for him (n = 10),
420.543 -> whether I will go for (n = 100), whether i will go for (n = 1000)
424.538 -> So it will only take a constant time,
426.247 -> I assume that (k1), that the time it is taking in running,
431.405 -> it will be constant
432.766 -> it will be constant, ok
434.807 -> After that the time it took, the inner part,
438.082 -> that too will remain constant, I have accepted that (k2)
440.001 -> I am not talking about the outside of the for loop,
441.238 -> I am talking about the work inside, that will remain (k2)
443.485 -> And I have accepted it (k3) within the work that is being done, okay.
449.069 -> what to see now
450.745 -> If I want to find out its time here, how many times it is running
455.999 -> then i will write (k1+ k2n+ k3n)
461.294 -> Because this is also (n) time running, and this (n) time is being run
463.87 -> Now what will I do with this rule! remove the non-dominant term
467.815 -> Now taking (n) common from this, n(k2+k3), which is a constant
472.426 -> I will accept it in (k4) and (n*k4) I will do it,
475.768 -> and it will happen O(n)
477.903 -> Why did this O(n)? this O(n) happened for this
480.507 -> Because I put the rule, drop the constant term
483.996 -> Drop the constant term
485.445 -> eliminate the constant term, ok
487.245 -> Eliminate Constant Term
488.956 -> So I dropped the constant term, so here's what happened
492.307 -> (k1+ k2n+ k3n)
495.085 -> (k1) removed from it first, (n) taken as common
497.011 -> (k2+k3) persuaded (k4)
499.011 -> and then O(n)
501.009 -> So if there is a different for loop then that too takes O(n) ,
504.8 -> if you will also add one more (k4)
506.665 -> If you do it (k=0), (k
510.866 -> Okay, it will not (n²)
512.85 -> ok remember you this thing
514.352 -> Now I want to take one more example which is important
518.826 -> So here I am taking one more example,
521.027 -> after that we will solve the question
522.361 -> It is not that we will not solve the question.
523.958 -> But by taking an example here, I want you to understand that
526.979 -> how these problems are approached, Okay.
530.703 -> So this which is our for loop, I will build on it only
534.894 -> So I'll make a little space over here
537.757 -> On top of this, suppose (k1) it is taking time,
539.762 -> whatever code we wrote, I will keep it above.
541.951 -> And down here I'll put another for, on top of it
545.797 -> suppose this is nested for loop (i=0; i
550.947 -> And inside this for loop there is another for loop, let me make it (j)
554.761 -> Let me make it (j), okay
557.174 -> And at the same time, here's what I'm (j
561.67 -> it's going to (n) times, its this off, its this off, okay.
565.474 -> So whatever this is it's inside an else for loop,
567.587 -> so it's a double nested for loop
569.256 -> Inside the for loop is the for loop, okay
570.862 -> I should have become a intend,
572.004 -> for starts from here, looks a bit good
573.866 -> But you understand here,
575.319 -> how will it be if I make some space here?
578.573 -> If I start from here for, so there's this loop inside it, okay
584.126 -> Now tell me how it's time complexity will come out
586.57 -> If you see this and say that this too O(n) is like the previous one
590 -> So it is not O(n) I will tell you why it is not O(n)
592.825 -> What do I have to do, I have to get out T(n) what I told you guys
597.713 -> There will be some code on it which will take (k1)
600.098 -> Now I have become so smart, by doing questions,
602.704 -> and you will be done too
603.783 -> That (k1) it is will going to be non-dominant,
606.273 -> if constant is being added then we will remove it, okay
608.929 -> So this (k1) does not make any sense,
611.258 -> but even then I will write one more time.
612.662 -> We will ignore this (k1) again in questions,
615.16 -> I will not tell again and again
616.193 -> So now you have understood that if a constant is being added,
619.448 -> Time,
620 -> do not take it. okay.
620.892 -> And why not take it, we have seen it
622.443 -> because it has to become non-dominant like that later
624.246 -> So (k1) and now after that (k2) is working
628.747 -> but how many times this (k2) will run
630.977 -> Okay.
631.7 -> so how do i find out
633.939 -> so (k2) will work, but how often
636.748 -> it will have to be seen here
638.722 -> And how will I see (k2), and how many times it will run
641.764 -> So once the value of (i) will be zero(0)
644.032 -> Ok, So once the value of (i) will be zero(0)
646.073 -> and then the value of (j) will be zero(0)
649.394 -> So once so (i=0, and j=0) will run for
652.786 -> Okay
653.653 -> Then the value of (i) is zero(0),
655.28 -> since the first inside loop will run,
656.528 -> once the value of (i) is zero(0)
657.622 -> then (j=1) will become
660.42 -> Then (0,2...n) then it will go on till (n)
666.014 -> So once the value of (i) the (n) times are running out,
669.008 -> watch carefully, watch very closely
671.17 -> Then later I will ask the question, then I am telling if it is not done.
674.633 -> value of (i) will be zero(0), and what is happening after that,
678.783 -> (n) times running
679.78 -> then the value of (i) will become (1), it will run again (n) times
683.636 -> Then the value of (i) will be (1), (n) the times will run
687.243 -> So what will happen over here, it's running (n) times, for (i=1)
691.297 -> Well, for (i=1), it's running (n) times
693.693 -> and then it is running (n) times, for (i=1), for (i=0)
701.473 -> For similarly (i=n) it will run (n) times too, ok
705.494 -> And when (n) you will add (n) times, what will come
708.404 -> When you add (n), (n) times
711.047 -> till n(1+1+1 and i=n), ok
714.072 -> It will be (n-1) because I am taking the index (i=0)
716.842 -> then (i=n-1) will be
718.189 -> and here is (n-1)
719.611 -> So it's going up to zero(0) to (n-1), it's okay
722.833 -> So if you would do (n) times, it was for (i=0)
727.929 -> then how many numbers will be in it! (n) will remain
730.598 -> then it will be (n), it will run for (n²) times
733.506 -> is it clear to you guys
734.507 -> I didn't want to say directly that this will run for (n²) times
737.31 -> This is what you guys should know, why it will run for (n²) times
740.245 -> Because look at the value (i) of zero(0) for (n) times it will run
743.325 -> Then for the value (i) of (1), (n) times will run
745.103 -> Then for the value (i) of (2), (n) times will run
746.732 -> Then for the value (i) of (n), (n) the times will run
749.331 -> When it was going on (neither) times,
751.492 -> went on doing it (+n) in the same number of times
752.799 -> Well, I am doing add only in as many times as it is going on here.
755.26 -> So that's why it will be (k2n²)
760.288 -> it will be (k2n²)
761.74 -> So how did this happen (k2n²),
763.719 -> this is beyond the scope of this course,
766.358 -> it is very pure and simple mathematics
768.259 -> But even then I told you guys
770.102 -> If it's not clear to you why it will work (n²) times
774.341 -> So I'd say let's go look at it for 3 and 3
777.156 -> and print here (i,j)
779.622 -> and make a count variable and count it,
782.493 -> how many times it is running
783.3 -> You write (c) program, write in Python, write in the Python,
785.899 -> write in Java, write in the Java
787.25 -> But when there are 2 loops inside one,
790.901 -> then that will run for (n²) times
792.526 -> And if another loop is given inside it, then it will run (n³) times
795.606 -> And if another loop is given inside it, then it will run (n^4) times
798.365 -> Okay
798.916 -> Because this you guys should have clarity
801.004 -> because many times you will get to see such patterns.
803.598 -> Then you will not sit down to do this,
804.892 -> I have got you to understand what we are doing, okay.
810 -> So now seeing such term should not take you so much time
814.461 -> that you are saying that it is non-dominant
816.554 -> This is Constant, O(n²) is
818.807 -> Tell me as soon as you see it, let your eyes ignore it.
821.889 -> And by looking at the bigger term, take the term with the highest degree:
825.831 -> It will be O(n²), okay.
827.286 -> So this is the simple technique that we will use that
830.39 -> It's not much technique, it's just 2-3 techniques:
832.983 -> read the definition of big O, big Theta (Θ), and big Omega (Ω).
836.659 -> That was just for clarity
838.56 -> Here the work has to be done for this
840.872 -> Okay
841.372 -> from here the work will be done.
842.667 -> There are some more cases in which what has to be done
845.066 -> when there is a recursive call
846.369 -> then we have to count the recursive call
848.176 -> So it takes a little effort over there
851.076 -> But,
852.186 -> but what happens
853.445 -> What is the answer of big O, you people get out,
857.261 -> when there is AIM then
858.979 -> we approach the problem in a different way.
861.065 -> I will solve some problems for you guys.
863.13 -> Here were the tricks that I told you guys that
866.01 -> If there is a double for loop, then it becomes straight (n²)
869.296 -> But never solve the question blindly,
871.676 -> because you people can be trapped.
873.544 -> Maybe he can put a recursive call inside it,
875.769 -> to complicate the query a bit
878.044 -> Those kind of questions are a bit high level, but we will do that too.
881.224 -> and will increase the level, go a little above from simple questions
884.006 -> So let's solve the question, it is very important
886.254 -> Alright Guys, now the time has come to solve some problems
889.723 -> And I have kept a complete set for you guys here.
892.887 -> If you haven't accessed this playlist yet
896.264 -> Which playlist, data structure and algorithm's playlist
899.022 -> So make sure to access it man
900.879 -> Because all the videos are going to come on this, I will put all the videos on this
904.058 -> And what am I going to do here now?
906.447 -> I will solve the problems which I have shortlisted for you guys.
911.433 -> and i am using one note here,
913.763 -> a lot of people ask which software do you use it
916.345 -> And I blow up in the editing, which is the part above,
918.978 -> that's why you see so much
920.252 -> In some videos you guys ask what software is this
922.692 -> so it's okay I'm not flying it now
924.609 -> I hope I will be able to explain you better here, in one note
928.758 -> What is here that I have made a notebook, in one note,
931.86 -> and the document which is here, I will convert it to PDF anyway
935.45 -> I have handpicked some questions here
938.529 -> which I am going to give to you guys here.
940.6 -> And I have also given their programs to you.
942.992 -> so you see here I have opened this folder, in visual studio code
947.25 -> So you people will come to know here.
949.248 -> that I have also made some programs.
950.871 -> And along with that,
952.769 -> I have created a folder named Time Complexity here.
955.867 -> inside which I have put this one note notebook.
957.95 -> ok so i have given this question here very clearly
960.897 -> then there should be no problem.
962.568 -> So I'm here, back, in my one note notebook
966.785 -> And let's tackle the first question,
968.451 -> and I have kept the programs of the questions which are here.
971.107 -> So what will I do, i will do close to the right
973.425 -> And you guys see the program of the first question here,
976.957 -> and first of all see what this question is saying.
978.826 -> So this question is saying that
981.532 -> Find the time complexity of the function
984.907 -> (Func1) function in the program shown in
987.691 -> program1.c as follows, okay
990.747 -> So by a program1.c is a file
993.823 -> What is this file? It has a function and it is (c) program obviously
998.879 -> Since I am doing in (c) language,
1000.301 -> if you do code analysis in Java, Python or any other language
1003.947 -> then the steps will be the same.
1005.207 -> Because even if you come from another programming language
1007.562 -> nothing is going to be change
1008.532 -> Because data structure is algorithm, it is a study
1013.097 -> that does not depend much on programming language.
1016.094 -> Because in that study, the implementation will be different
1020.199 -> in different programming languages.
1021.532 -> You Can Totally Follow If You Are Using other Programming Language
1025.498 -> So here I will set a pen, and here what I will do
1029.878 -> i will solve this problem
1031.414 -> So it's saying that
1032.517 -> Find the time complexity (Func1) function in the program
1036.851 -> shown in program1.c as follows
1039.241 -> So what's in here is a function by doing (func1), it's an array
1043.652 -> and this is the function by doing (func1)
1045.4 -> and what is this array doing
1046.533 -> It is passing the array (func1) to the array,
1050.117 -> and see what (func1) is doing with that array
1052.098 -> So here int sum=0; is coming by writing,
1055.265 -> and here product=1; is coming by writing
1056.975 -> So basically it is calculating the sum and product
1060.096 -> Look, if you look at it, there is a skipping of the array, which is 3
1063.169 -> and it will go from zero(0) to 2(n-1) here this loop
1066.047 -> Just like I told you a while back that
1069.446 -> when you have to analyze an algorithm,
1073.226 -> first of all you break it into fragments.
1074.761 -> So what will I do that I will break it first in this fragment
1077.362 -> And I'll name it as (F1), ok
1079.912 -> So I named it (F1), I will name this fragment as (F2)
1084.074 -> I'll name this fragment as (F3), ok
1087.735 -> So we've got 3 fragments now
1089.516 -> F1,
1090.192 -> F2,
1091.027 -> and F3
1091.942 -> so the time of (F1+F2+F3) will be that
1095.256 -> I will take as the overall time of the whole function
1097.648 -> What will be the time of (F1), some constant will be
1100.015 -> because you are doing sum = 0 and product = 0 each time
1102.867 -> It is not depending on Array's length
1104.89 -> so i'll accept it (k1) ok
1106.8 -> ok so i got it as (k1)
1108.114 -> what will I believe as (F2)
1109.518 -> I cannot accept (F2) as (k), i will accept it as (k2*n)
1114.128 -> Because this loop is running (n) times,
1115.353 -> let's assume (n) of the length, it is running (n) times look here
1118.055 -> so you can also write the length here
1120.36 -> Because I have written the name of the variable here a little longer,
1123.185 -> that's why I am not writing the length.
1124.691 -> The length which will be exactly
1125.966 -> that is going to be the variable input,
1127.274 -> call this function
1127.897 -> then (F2) as (k2n) and (F3) as (k3n)
1132.274 -> ok so i have already told you guys here
1134.525 -> Now here I have used (i and i)
1136.573 -> I'm free to use it
1138.696 -> I have done it here (i) and I can use it again in the second loop.
1141.532 -> and (j) can also use
1142.522 -> so don't get confused by that
1144.233 -> So now if I find a total time complexity
1147.165 -> That is, if I T(n) come out, then what will it be?
1149.842 -> T(n) will be done as T(n)=F1+F2+F3
1156.433 -> ok it will be happen
1157.654 -> and (F1+F2+F3) will become (k1+k2n+k3n)
1165.405 -> And what I will do here is that I already told you that
1168.903 -> you can drop the non-dominant term
1170.849 -> so i will drop it
1171.99 -> And I'll go on with only this
1174.635 -> And now I will not write equal here because
1177.111 -> I have dropped non-dominant term for this
1179.413 -> And i will write here (k2+k3)n
1184.014 -> what can i write to and (k2+k3)
1185.848 -> (k2+k3), I can write the second constant
1189.064 -> and I can write as (k4n)
1190.63 -> So that's why this algorithm is O(n)
1193.533 -> ok so O(n) will run in time, where (n) is the length
1196.777 -> Since the length is given in the question,
1198.414 -> then I will report it by doing O(length)
1202.063 -> Wherever I have to answer, I will say O(length)
1204.47 -> Because the algorithm it is talking in terms of length
1208.197 -> over here you see it is talking in terms of length
1209.987 -> This is going to be a length variable, this (func1) function
1213.02 -> I hope you guys understand it
1214.771 -> So the answer is O(length), Okay.
1217.656 -> Coming to the next question
1219.724 -> By the way, I have given this program1.c to you,
1222.469 -> so you can watch it by running
1223.909 -> For different inputs you can see by running
1226.362 -> Or if you want to implement it in any other programming language
1229.855 -> Feel free to do that
1231.596 -> Feel free to do as well
1232.807 -> you can do that too, ok
1234.707 -> So guys here let's move on to the second question
1238.864 -> What is this, Find the,
1240.378 -> I have written fine here, let me correct it
1242.692 -> I wrote fine above also, find this man, this is find
1246.447 -> Never mind, these small mistakes are made
1248.659 -> Find the time complexity of the Func function in the program
1251.913 -> from program2.c as follows
1254.436 -> So look at this program,
1256.04 -> I have also made it here by doing program2.c.
1259.588 -> So you guys can also see by opening this program2.c.
1263.203 -> Otherwise, you don't want to see this program,
1266.466 -> even if I have written it here,
1268.597 -> then you should not have any such problem.
1270.438 -> I have this program inside one note
1272.922 -> I have shared this doc. with you people,
1275.031 -> you can take it from the description
1276.382 -> Look here what is it written, what is this happening
1279.13 -> First of all I will do, I will not write quickly (k1) here
1282.01 -> Let's write for another problem (k1) here
1285.158 -> Because you know I wrote (k1) for another problem,
1287.948 -> I know (k1) to be eliminated
1289.641 -> but still I wrote (k1)
1291.244 -> Now look inside for is a for
1292.891 -> When there is a for inside a for,
1294.425 -> and how many times to iterate (n)!
1296.28 -> it is going to [0,n]
1297.566 -> i.e. this loop will run, [0,n]
1301.305 -> ok, and it will run from [0,n]
1304.331 -> else if it's going to be [0.n]
1307.022 -> and it's also going to be [0,n]
1308.091 -> i.e. for 0, (n) times it will run
1310.311 -> OK, so this will run 0 for (n) times, then 1 for (n) times
1316.685 -> then it will again 2 for (n) times
1320.671 -> And so how long will it go on, it will run (n-1) for (n) times
1327.931 -> So here I do (n-1)n
1331.08 -> Here I put (+)
1332.594 -> and here if I assume its time complexity, (k2)
1337.225 -> that it takes (k2) time
1338.912 -> So here will come nk2, nk2, nk2, nk2,
1341.904 -> and out of all I can (k2) take the common
1343.68 -> ok so you understand what i'm saying
1346.07 -> Here I can take the common (k2)
1348.046 -> So look at me here, if I do it by putting arrow
1351.178 -> that is the solution to this problem.
1353.069 -> So (n) how many times it is coming, (n) it is coming in all
1356.7 -> So (n) can be taken out, so I can come out (nk2)
1359.44 -> after that i will get (1+1+1+1+1),
1365.005 -> how many times will this (1+1+1+1+1) go here
1367.774 -> It will go, if you look carefully above it is written (n) times
1371.689 -> So what will happen if I write 1 for (n) times as (1+1+1+1+1)
1376.672 -> So surely it will be (n), what will happen, it will be (n)
1381.163 -> so this will be (k2n²)
1383.483 -> So here I write this (k2n²) so it is done O(n²)
1388.01 -> So anytime you see the double for loop,
1390.61 -> and it's going to [0,n], [0,n]
1392.492 -> And there is some constant work going on inside it so it means it is O(n²)
1395.861 -> OK, so we've got to look at problem no.1.
1398.832 -> We understood it because it was O(n)
1400.449 -> And there was a very simple problem, problem no.2 also
1402.754 -> But this is a very basic problem of big O
1404.881 -> We are going to see a problem here that will challenge you.
1409.99 -> And I'm telling this is a bit challenging problem
1412.436 -> ok i am already telling this i am announcing this
1415.173 -> That's why you guys don't think that if it didn't happen to you,
1418.017 -> that it didn't happen to you, we are useless
don't think so
1420.967 -> I have not given this to you people to down your confidence
1424.925 -> Rather what I have done here just to encourage you a little
1428.624 -> that we can solve all kinds of problems here
1431.14 -> This concept applies everywhere
1433.359 -> Consider the recursive algorithm above,
1435.892 -> Should have written below not above, but never mind,
1438.652 -> I'll make it correct, I do it below
1442.732 -> where the random (int n) spends one unit of time to return a
1448.298 -> random integer, okay
1449.289 -> So here's a random function that takes one unit of time
1452.37 -> which is evenly distributed within the range [0,n]
1455.862 -> I have written 2 times [0, n]
1457.335 -> I typed it very quickly, I have to correct everything
1460.509 -> If the average processing time is T(n),
1463.509 -> What is the value of T(6)?
1465.145 -> So you have to find the expression of t(no) here,
1467.551 -> how long is it taking?
1468.815 -> that this is our function how long did it take
1471.432 -> It just has to come out, T(n) has passed, so T(6) will also found
1474.082 -> So what's the question here, the question is you find T(6)
1478.525 -> so T(6) is a small number
1480.288 -> If I directly solve for T(6)
1482.44 -> So maybe my work will be done here
1484.444 -> Okay!
1484.944 -> But what will happen, what will people do that
1487.376 -> try to derive the expression of T(n), which is possible
1490.801 -> I'm not saying it's impossible
1492.312 -> But according to me (6) is a pretty small number
1494.825 -> and you guys solve the problem directly,
1497.538 -> solve T(6) only then it will be good.
1499.78 -> So what shall I do here,
1500.979 -> I will try to solve the problem directly for T(6) only.
1504.001 -> And if this is a simple problem,
1505.451 -> then the expression of T(n) can also come out
1507.08 -> So here let's see what is happening in this function.
1509.162 -> First of all (int i;) I will call it (k1),
1513.197 -> that this thing is doing some constant work.
1515.16 -> Here if there is (n≤ 0), then it is getting return
1519.04 -> and after that this one below won't work if it is (n≤ 0)
1523.496 -> But what is happening here is that
1525.26 -> this recursive is calling a random function
1527.689 -> Which is taking one unit of time
1529.558 -> So what shall I do, I will write this as 1, okay
1532.374 -> and i would say it is taking one unit of time
1534.596 -> And the rest is written in it that if it is taking one unit of time
1538.402 -> So we can assure the rest of that is taking negligible time
1541.043 -> So I'll zero it here (0)
1543.435 -> And you know why I changed (k1) to 0
1545.023 -> I set (k1) to 0 because it is written here that
1547.262 -> it is taking random one unit of time.
1549.001 -> and it would have been fair
1550.695 -> If I had written here that the calls which are other than random
1555 -> are not taking much time, okay.
1556.887 -> If I had written this then it would have become more fair.
1559.637 -> So let me add to this that
1561.171 -> the rest of the calls are not taking much time.
1564.745 -> So here you guys see how many times random calls will happen
1567.605 -> this is the question
1568.475 -> So if it is taking random one unit of time
1570.69 -> you have to tell that
1572.077 -> if the average processing time is T(n)
1573.788 -> then what will be the value of T(6)
1575.334 -> So I have to tell you how many times random calls will happen
1578.698 -> For (T=6)
1580.141 -> So over here now look what I'm doing,
1581.33 -> and I'll tell you what Random is doing here
1583.504 -> I should also have written what Random is doing here
1585.614 -> A little question is incomplete but I will complete it
1588.585 -> But now let me tell you what the question is
1591.183 -> I just complete it
1592.099 -> What will Random do if you write your random as 6?
1598.661 -> So what will it do, it will give you the middle of [0,6]
1602.117 -> So look here I have written
1603.526 -> return a random integer which is evenly distributed within the
1606.348 -> range [0,n]
1606.848 -> So it is any number in the middle of [0,6].
1608.251 -> will give to you by written, okay.
1610.244 -> i.e. is just random,
1611.885 -> anything between [0,6] you will get by written, okay.
1616.079 -> So I do one thing, I change the color here
1619.631 -> And I do in color change, I do in red color
1623.385 -> Because what if I do it in red color, then I can do it in purple
1626.998 -> So you will know the difference between ques.1 and ques. 2.
1629.53 -> that these two are the solution of different question
1631.851 -> now look what i have done here
1633.359 -> This function is written so
1635.294 -> I just want to find what this T(6) is doing
1637.481 -> If T(6) I wrote here,
1639.558 -> Now I'll do it with recursion,
1641.138 -> T(6) is recursively calling itself
1643.081 -> For T(i) and T(N-1-i)
1646.664 -> So when T(6) will call, pay attention to what I'm doing here
1651.135 -> T(6) will call when over here, then it will be 0 times over here
1654.634 -> So once it will call Random because it is not (6≤ 0)
1658.467 -> so it will go to else, it will not go into if
1660.947 -> Watching carefully you guys, won't go to (if) it will go to (else)
1663.798 -> ok so i found out that he is going to (else) for (T=6)
1667.455 -> And one unit of work is also doing that
1669.907 -> So I will add here that this one unit of work is doing
1672.515 -> So here I will write 1 in this way
1675.44 -> Along with one unit of work he is calling his 2 child units of function
1682.229 -> and what is that, T(i) and (n-1-i)
1686.335 -> But here do you guys see one thing
1688.386 -> that (i) it is random, see here that (i) is random
1691.173 -> which can be anything between [0,n-1]
1693.539 -> i.e. in this case it can be anything between [0,5]
1696.874 -> So what do i take the value of it.
1698.582 -> now because here they have given that it is random
1701.733 -> So I can take anything, it means that whatever it is, the answer will be same.
1705.852 -> The answer will be same
1706.704 -> What did I say, I did it because
1709.077 -> the question itself is something like this
1710.376 -> Now here I will also tell you why the answer will come same
1713.346 -> But now let us assume here that I will take any value of (i).
1718.372 -> The number of calls that will be there,
1720.005 -> whatever the calls will be of T,
1721.697 -> the number of calls that will come in the same
1723.425 -> So here what we will do now,
1724.847 -> suppose I have made the value of (i) here 0
1727.771 -> suppose it became 0
1729.051 -> So if I make the value of (i) 0, then this function will become 0
1731.99 -> So this will be T(0), ok
1734.021 -> and if you guys look over here
1735.798 -> T(0) is something that doesn't work
1737.742 -> Because it will return here, it will not come at random
1741.552 -> This call for (n=0) ,0 will work
1745.284 -> So here I will write 0 by putting an arrow on it,
1747.145 -> that means I do not want to add anything in T(0)
1748.842 -> and at the same time it will call T(5)
1751.494 -> Okay.
1752.272 -> After that I will break it into T(0) and T(4)
1756.934 -> Okay.
1757.83 -> into T(0) or T(4)
1759.562 -> After that I will break it into T(0) and T(3)
1763.958 -> After that I will break it into T(0) and T(2), okay
1766.835 -> that I will break it into T(0) and T(2)
1770.118 -> Similarly I will break it into T(0) and T(1)
1774.106 -> I will break it into T(0) and T(0)
1776.834 -> which means it's nothing
1778.832 -> Now these T(0), T(0) calls are coming,
1781.663 -> they are taking zero units of time.
1784.48 -> But it took my, one unit of time
1786.326 -> it took my, one unit of time
1787.747 -> it took my, one unit of time
1789.064 -> it took one unit of time
1790.381 -> and how much is it
1792.294 -> How long did it take 1,2,3,4,5,6
1795.704 -> This means 6 times, here will be a random call
1799.101 -> So the answer will come 6
1800.658 -> Okay!
1801.516 -> Now you will say that you have assumed one thing here
1803.71 -> that the value of (i) is always 0.
1805.212 -> but the value of (i) can be randomly anything between [0,5]
1808.585 -> So will the algorithm not depend on it?
1810.697 -> Look what is happening here that
1813.003 -> what it is doing child processes is giving, giving, giving
1815.801 -> continues to produce, until it breaks and almost ends
1819.863 -> Because the child process it is giving
1821.06 -> is calling the recursively function,
1822.78 -> it is doing a smaller than itself
1824.234 -> T(6) is not doing T(6), T(6), T(5), T(0) is doing
1827.634 -> If I do T(1), T(4) also here
1830.084 -> You guys try and see what will happen
1832.032 -> even then it will keep breaking, it will keep breaking
1834.064 -> till it becomes T(0), T(0)
1836.24 -> This will continue until there are all leaf nodes everywhere.
1839.13 -> And in that case also you will get 1,2,3,4,5,6 calls
1845.538 -> I have written a function of this,
1847.125 -> I have made a program for it, program3.c
1849.867 -> infact it's program4.c
1852.846 -> or it is program2.c or program4.c
1855.161 -> yes there is program4.c
1856.335 -> So I have implemented random over here
1858.365 -> And what I have done here is that (this) is written,
1862.01 -> (this) means whenever there is a random call then this printf will also be run
1866.25 -> So the number of times (this) printed means that
1869.282 -> the number of calls will be same
1870.355 -> So, if I run this, then you guys will see that
1873.259 -> (this) will be printed 6 times.
1874.875 -> Okay, So 1,2,3,4,5,6
1877.174 -> If I run back then 1,2,3,4,5,6
1880.201 -> Calling 6 times (this)
1881.534 -> So here is what is random, which is giving the value random
1884.306 -> is giving that randomly between [0,n]
1886.381 -> So it is not necessary that you verify this mathematically.
1890.162 -> But since this question has been asked,
1891.881 -> so you can take anything randomly.
1893.583 -> If your interviewer says as if after
1896.602 -> I have taken randomly here then will not depend on it
1899.398 -> If you are not sure then you can tell your interviewer that
1902.435 -> I am not sure whether it will happen or not.
1904.788 -> But because I told myself that I can take anything randomly,
1907.483 -> so I took anything randomly.
1909.203 -> Whenever you give interview, a coding interview especially
1912.517 -> So you don't always have to be right there
1915.768 -> you be so honest
1917.05 -> Along with others, show him something,
1919.818 -> because if he is asking you a question
1921.407 -> and you are blank,
1922.134 -> he will not know what do you know.
1924.05 -> But if you're approaching him in some way
1926.352 -> If you're approaching him like this, you're making a recursion tree
1929.098 -> So he will know that yes man you know all these things
1932.39 -> you have clear concept of big O
1933.809 -> You know how many times random calls are happening here,
1937.533 -> that have to count.
1938.206 -> The function given here is that
1940.892 -> the function is taking one unit of time.
1942.664 -> If you understand all this on your own,
1943.879 -> then all these things matter to you.
1945.84 -> Okay.
1946.579 -> This question was a bit tricky
1948.378 -> and I had to take this tricky question
1950.033 -> If you don't understand it, I would say look back
1954.06 -> So what have you done here, I have broken it down only
1958.273 -> I've broken it down when it's run for (6)
1960.915 -> You can proof this by breaking it for (n)
1964.355 -> It can be proved that whatever the value is at random,
1967.218 -> it will not depend on what your (i) value is.
1971.357 -> unless it bumps [0,n-1]
1973.487 -> as long as it's inside [0,n-1] sorry
1976.123 -> As long as (i) is on [0,n-1], it will not matter
1980.073 -> The number of calls will remain the same (6)
1981.504 -> I have shown here by practically running that
1984.001 -> this random which is generating the numbers randomly
1987.201 -> I have run it even then (6) is coming,
1989.084 -> and again and again (6) will come, okay
1990.633 -> You can also check it by putting it in the loop
1992.485 -> whether (6) is coming or not, okay.
1994.716 -> So back to one note
1996.401 -> And look here what the fourth problem is saying,
1999.316 -> and the fourth problem is very simple
2000.506 -> Which of the following are equivalent to O(N)? Why?
2004.447 -> Which of the following is equivalent to O(N) and why?
2008.785 ->
let's look at the first
2010.652 -> So it is O(N + P) and I know where (P < N/9)
2015.77 -> i.e. it's a non-dominant term, okay
2018.132 -> What is (P), non-dominant term,
2019.406 -> here it is clearly written in the question
2021.135 -> I do one thing, which is my pen, I change it a little.
2025.238 -> i do it.
2026.462 -> So look it's non-dominant term as you see
2029.095 -> Need a little thin pen man
2030.813 -> Yes, it is a non-dominant term, so what can I write it,
2033.901 -> can I write it O(n) so it is O(n), okay
2039.149 -> Let's look at this (9N-k)
2041.569 -> where (k) is a constant, so I can eliminate the constant like this.
2044.457 -> So then it will be O(n)
2046.751 -> Because I will eliminate (9) also
2048.354 -> It got eliminated because of the non-dominant term,
2050.001 -> and it got eliminated because of the constant, right
2052.191 -> So this constant will become non-dominant
2054.741 -> in front of (9N) for very large (N) values
2058.206 -> and (9) is a constant with (N) so I removed
2061.009 -> It is also O(n)
2062.019 -> So it is, this it is, and see this is it
2066.127 -> This is also visible because
2067.087 -> (8log N) is a non-dominant term
2069.302 -> It won't be able to dominate in front of (N)
2072.187 -> because (log N) grow a lots of slowly
2073.709 -> (N), grows more than (log N)
2075.496 -> if I draw a graph of (log N)
2076.895 -> So it will come something like this,
2078.373 -> and (n) will come like this
2080.694 -> (log N) will come like this
2082.057 -> So for very large values, what it is (N)
2085.393 -> will always be above (log N), Okay.
2086.818 -> It is also O(N)
2091.487 -> see this (N + M²)
2093.82 -> Now here if this (M) is a constant
2095.722 -> I should have written here in brackets, where (k) is a constant
2098.647 -> Should have written like this, I didn't
2100.764 -> But I should have written here (k) is a Constant,
2102.505 -> I will add to the question here (k) is a Constant
2104.675 -> Because if you do not know what (k) is, is a constant or not
2108.556 -> like here there's (N and M)
2109.895 -> It is a O(N + M²) algorithm
2112.434 -> It cannot be written as O(N) because (M) is also an input
2115.4 -> so you cannot ignore it.
2117.337 -> So (C) is O(N), and (D) is not a O(N)
2120.231 -> And in the question which I have not added the details, I will also add all that.
2123.436 -> That's Doc. i will update what it is
2125.484 -> So that when you solve the question without looking at the question,
2130.536 -> then you will not have a problem.
2131.685 -> Okay
2132.501 -> Now let's see here what is the fifth question
2134.981 -> So we have solved 1,2,3,4 questions
2138.063 -> very good
2138.98 -> Ok so this also got solved, I put a tick on it too.
2141.813 -> Now, here I see that
2143.976 -> The following simple code sums the values of all the nodes in a
2149.781 -> balanced binary search tree
2151.008 -> Now here I will tell you a little bit about the search tree,
2153.906 -> I will not tell much, I will tell a little, okay
2156.045 -> And whatever is there, your work will be done
2158.615 -> I will tell you further, I will tell you very well
2161.673 -> do not take tension, you guys
2163.633 -> But for now just for this question
2165.362 -> What is a Binary Search Tree, understand it as such that
2169.693 -> It's a node, and it's something like this,
2174.33 -> so I'll zoom in a little bit
2175.916 -> So it goes something like this,
2177.737 -> we have a node, we have a node here too
2181.202 -> and back inside it has a pointer
2184.074 -> which is pointing to another node
2185.712 -> And it's pointing to 2-2 nodes, okay
2187.874 -> So if you read about Balanced Binary Search Tree then
2191.246 -> Well, I will tell you further, but if you do not know, then understand that
2194.783 -> there is a structure here, which has 2 pointers.
2197.988 -> Which are pointing to different types of nodes, like this
2201.749 -> Now look what this algorithm is doing
2203.73 -> Because this question is very straight forward,
2205.277 -> here you will not have to go into the details,
2207.037 -> this question is such that it will be solved on seeing it.
2209.125 -> I have taken an example like this
2211.061 -> So you guys look at this
2212.808 -> So what is it doing, whatever it is doing,
2215.584 -> because it is written here that it is sum all the values.
2217.707 -> Sums the value of all the nodes
2220.441 -> It itself showed that it is doing sum : Value of all the nodes
2224.106 -> Question is speaking one thing by itself,
2225.305 -> then the question will never contradict itself.
2227.214 -> So the question itself told that it is counting the value of all the nodes.
2232.173 -> And it's saying what's its runtime
2234.671 -> If I assume that which is (n),
2236.279 -> I will write here that (N) is the number of nodes.
2241.475 -> Number of nodes
2244.682 -> So what will be its run time, you tell me by commenting,
2247.763 -> I want you to tell by setting the time system
2249.769 -> What is it doing, first of all it will sum of it
2254.06 -> Then what is it saying that sum him, call him for this
2257.671 -> Then it is saying do a sum for it, if this node is null,
2260.292 -> that is, there are no other nodes below it.
2262.051 -> So what is it doing, returning 0
2264.342 -> And here the value of this node which is,
2266.882 -> will be summed up to be the backtrack.
2268.579 -> So basically this is a recursion, Okay
2269.902 -> But here I want to realize one thing to you guys.
2272.428 -> How much this code is working,
2274.686 -> this code is almost working same for every node
2277.601 -> OK, so for every node
2278.666 -> So the more nodes there are, it will be big O.
2281.794 -> A little bit I have told you directly here
2283.937 -> It will O(N) happen, I'm telling you
2285.751 -> but over here if you try to figure it out over here
2288.372 -> what it's doing
2289.458 -> It's calling this recursive function and it's sum for all nodes
2295.845 -> which is doing the work for it, is doing the same work for it.
2298.631 -> is doing the same work for it.
2299.804 -> And finally nothing is working for the nodes which are below,
2303.896 -> but when it will grow the tree,
2306.378 -> which is (N), number of nodes
2309.023 -> depend on its run time.
2310.887 -> So this I have directly told you here
2313.332 -> But again we will talk about Balanced Binary Search Tree
2316.491 -> And I solved this problem very quickly.
2320.73 -> So here you guys just keep in mind that
2323.955 -> never solve this kind of problem in a hurry.
2326.546 -> Now if you don't know the Balanced Binary Search Tree
2329.177 -> So maybe you can say this directly to the interviewer,
2332.22 -> that I don't know
2332.914 -> So this would be a very big red flag
2334.073 -> if you say that
2335.024 -> I don't know about Balanced Binary Search Tree.
2336.879 -> Then obviously he prefers to the person,
2339.829 -> to whom all these things come
2341.094 -> It's very simple: I will tell you next
2343.04 -> But for now let's move on to the next question:
2345.742 -> And on this question you can come back and come back and revisit on it
2349.551 -> and you can see it
2351.2 -> Because the query it used to depend on the Balanced Binary Search Tree
2355.115 -> But I told you with an idea that it is working same for every node
2358.76 -> so that's why it is a O(N)
2359.907 -> Because when it grows, this is the tree when it grows,
2362.959 -> the input size when it grows
2364.107 -> So it is working almost same for all the nodes,
2366.537 -> you can see here
2367.914 -> Because if node becomes null, node itself becomes null
2372.41 -> This node is not null right now, it is pointing to null
2375.52 -> ok so it points to null
2377.641 -> If you haven't read the binary search tree
2379.783 -> By the way, it's not fair that I will tell you all these things right now.
2381.79 -> i will tell you ahead
2382.855 -> But if both of these are pointing to null
2385.952 -> So what does it mean, it is doing the same work for this
2387.982 -> doing the same thing for the ones below: this
2389.869 -> if you look at it carefully
2391.367 -> So it is doing this for the below ones,
2392.611 -> and for them it is doing return (0)
2394.896 -> So it is working for all the nodes at the same
2397.045 -> the number of nodes it has will be its run time.
2399.211 -> So if you write the run time, then you can do k(n), T(n)
2402.359 -> and after that you can do O(N)
2404.422 -> So i think this is very clear,
2405.452 -> Your interviewer can sometimes give you a hint
2407.466 -> If you do not know Balanced Binary Search Tree,
2410.194 -> then he can tell you
2411.354 -> what is Balanced Binary Search Tree.
2412.941 -> And from there he will tell you that
2416.196 -> now you take the problem ahead.
2418.083 -> So i hope you guys have understood the problem 5
2420.442 -> So if it seems a bit strange, then
2422.758 -> am telling you to revisit it.
2425.367 -> after reading the Balanced Binary Search Tree,
2427.121 -> Okay
2428.091 -> Now look here what it is doing
2430.315 -> It's a little tricky, but it's not that tricky, but it's quite
2434.206 -> Look, what this code is doing,
2436.051 -> testing this code, whether a this number is prime or not
2439.542 ->
If you have already seen this code
2441.753 -> Then you guys can trust on this code here
2444.553 -> So it is saying itself: it is testing
2447.12 -> whether a given number is prime and not
2449.592 -> Okay!
2450.122 -> So it said itself in the question that I am checking
2452.786 -> whether this number is prime or not:
2456.53 -> Okay
2457.309 -> So over here if I do and analyze this code
2461.078 -> and then I will not consider it because it is a constant.
2463.669 -> ok, so this checking which will be done in: (k1) time
2466.169 -> Assume that as (k1)
2467.026 -> I will not write again and again in my time
2469.1 -> But let me analyze this: because it's coming here (N)
2471.541 -> I have to analyze that much part
2473.281 -> Now let me see how many times this loop will run
2476.026 -> just to see:
2476.877 -> and it will be (k2)
2478.739 -> And at first I will write T(n), (k1 + k2(N2)) as
2483.213 -> as many times as this loop runs,
2484.235 -> let's see how many times this loop will run
2485.53 -> So this loop is running, it is starting with (2) :loop
2488.833 -> Okay
2489.786 -> and going until it becomes i²=(n-1)
2494.833 -> When i²=(n-1), then its last executable will be
2501.667 -> Let me see: with what value of (i) it will work with
2505.048 -> So this will work for i=2, will work for i=3
2509.406 -> And how long will it last, what will be its final run,
2512.302 -> what will be the last run, what will be the value of final (i)
2514.323 -> It will be (√n)
2514.988 -> Look when the value of (i) is less than (√n)
2517.382 -> So any number which is less than (√n), will run till
2520.596 -> So let's assume that this is going on till (√n)
2522.601 -> It is not necessary that it should last till (√n)
2524.708 -> Since the value of (N) cannot be (N) perfect square
2527.327 -> But let me suppose that (N) is a perfect square
2529.06 -> Otherwise this (√n) of which will be our greatest integer
2533.227 -> It will go till there, Okay
2534.81 -> I don't want to get a bit complicated here,
2536.736 -> so you can assume it will last (√n)
2538.671 -> so the value of (i) is running for 2,
2540.307 -> is running for 3, so it will last for till (√n)
2542.058 -> So it will go approximately up to, (√n-1)
2547.329 -> this loop will run approximately (√n-1)
2550.396 -> If I use a rough idea so I can take it (√n)
2552.758 -> These are all constants, whatever will be behind it
2555.182 -> So if I solve this problem quickly then,
2557.15 -> I would say it will last till (√n)
2558.866 -> It almost always starts with (2),
2560.433 -> until (i) become (√n) or less than (√n)
2563.369 -> It's going up there, okay
2565.055 -> So it will last till almost (√n), so I can call it O(√n)
2569.119 -> So here you guys will have to apply approximation sometimes
2573.145 -> Because it can have constants in front, behind, (+), (-)
2576.382 -> but (√n) which will be dominant term
2578.752 -> when the value of (n) is very large
2579.901 -> And those constants won't stand before it at all
2582.337 -> So that's why it will happen O(√n)
2584.608 -> Ok, so we have solved the problem of (6) also.
2589.074 -> Now this is the seventh problem, it is very interesting,
2591.864 -> you guys see here
2593.111 -> Whoever I have called this prime
2595.091 -> should have given a number too.
2597.009 -> As if I am giving (18) to this,
2598.356 -> well I have made a mistake here: I will correct it
2600.492 -> I should have given an number inside this prime
2602.856 -> What is the time complexity of the following
2606.103 -> code snippet
2606.795 -> It has named this function: isPrime
2609.155 -> Okay
2610.076 -> But when you look at it carefully, you will know that
2613.028 -> it is not checking for prime number,
2615.028 -> it is doing something else.
2616.502 -> But your interviewer may ask you questions like this
2619.33 -> Because he will expect from you that
2620.711 -> you speak out of fear at once O(√n)
2623.015 -> Because you already have this problem,
2625.5 -> you have solved this problem:
2626.579 -> Because he wants you to get nervous,
2628.421 -> hustle, lurk O(√n) You speak quickly,
2632.206 -> and he will say wrong because in this: there is no (n)
2634.71 -> So what is it here that it is not fully dependent on (n)
2638.577 -> Because (n) is taking in input
2639.935 -> but (n) is not coming down anywhere.
2641.386 -> So this means it will be a constant, I can assume that (k1)
2645.025 -> Because no matter how big the value of (n) is,
2646.723 -> it is running only 10,000 times,
2648.775 -> so i can consider its time as constant
2650.686 -> And i can write T(n) as (k1),
2653.13 -> or i can write as O(1), i.e.
2655.971 -> running in a constant time
2657.84 -> Now again (7) questions which: what we do of big O
2661.805 -> And i hope this question will help you guys a lot
2664.571 -> I want you to raise some questions from anywhere of big O
2669.194 -> by searching the internet,
2671.194 -> Or if you are following any textbook etc.
2673.315 -> then you can pick it up from there,
2674.722 -> nowadays there is no shortage of questions.
2676.197 -> solve them by lifting them
2677.708 -> These (7) questions will help you a lot
2680.082 -> I will do one more thing,
2681.176 -> will make videos of more problems in future
2683.348 -> But according to me, we have time: to move on
2686.049 -> We take this concept forward
2688.215 -> the course of Data Structure and Algorithm:
2690.349 -> Because if I solve a lot of questions in big O,
2692.754 -> then I do not want to spend a lot of time in it.
2694.489 -> I told you guys that you can solve any problem of big O or any.
2698.64 -> And to solve some of big O's problems
2700.922 -> Whatever you guys were talking about, like the binary search tree
2705.146 -> We will talk about stack, queue etc.
2708.872 -> All of them can use to him,
2711.172 -> all those things can come mixed in it.
2713.294 -> And as all those things mix,
2714.842 -> we'll keep talking about big O again and again.
2716.761 -> So this is not the end of this topic
2718.825 -> This is not the end of time complexity.
2720.891 -> we will talk more about it
2722.725 -> But, i think for now this is enough for practice
2725.927 -> If you want to do more then it is a very good thing,
2727.505 -> but according to me right now, practice is enough:
2729.606 -> Next we will take more practice
2731.249 -> We will continue to practice the questions.
2733.103 -> so so hope you guys liked this video
2734.692 -> One thing I want to tell from my heart to all of you
2736.123 -> please share this playlist.
2738.001 -> I am doing a lot of hard work for you guys,
2739.744 -> I have made notes for you guys.
2741.408 -> You will also find the notes of this chapter in the description.
2743.95 -> And this is the sheet you will also get it
2746.306 -> I will give it to you by putting it
2747.741 -> I hope that you guys like these all things
2750.16 -> And you guys are enjoying this course
2752.163 -> That's all for now in this video
2754.743 -> Thankyou so much guys who watching this video
2756.971 -> And i will see you next time.
Source: https://www.youtube.com/watch?v=STL8ESuETmM