that was the best and easiest way one can learn. I m fascinated by how easily u r able to create the logic in ur head and implement it. The flow of logic u have is really unique and thanks for sharing the knowledge with us as it is really easy to understand from ur videos. An upgrad faculty of IIIT B has been teaching it with very bad pronunciation and logics and i have been trying to understand this simple calculation from his video since an hour but here only after a single view I am able to understand the approach that i need to make for such calculations. Thanks a lot and may you rest in peace.
Hi Amar, If you see, if (n == 0) statement will always be executed.. .. return may not be executed always. That's why adding up 1 unit for the if condition. :)
Hi, As per your previous tutorial, you mentioned like whenever there exist and conditional statement we should take up the worst case scenario and we should not add up the time complexities of both conditions because its either-or right. So in that case the above complexity should be calculated as T(n) = T(n-1) + 2 // 2 is constant time in worst case scenario T(n) = T(n-2) + 4 (i.e) T(n-k) + 2k when n-k =0, k=n => T(n)= T(0)+2n = 2n => O(n)
it look like old video, but very interesting, uploaded when l was in class 4 and now watching it in third year university degree level, how interesting this video is wow, keep it up bro
man, why this video isnt in the compilation of the time analysis? btw...the important thing I wanted to say is GJ! TY VERY MUCH!!! you are very clear and I understand all that tstuff ;D ty
For anyone else wondering this is just badly written index notation. The (n-1)+3, (n-2)+6.. (n-k)+3k are the index positions. It is not T multiplied by (n-1)+3 etc
Sir in this video you are taking T(n)=T(n-k)+3k but According to the first equation T(n)=T(n-1)+3 the last equation must be T(n-(k-1))=T(n-k)+3k in the factorial recursion example
I think its wrong .... You said in the previous leson that we do not add complexities in conditional statement , rather we take the max of the conditional statements. At 2:10 although the value is correct i.e. t(n)=t(n-1)+3 but one 1 in the three comes from return statement not from the if statement.
In that video, you directly took O(n2) regardless of if statement execution.. So little confused. So even in that case if condition will be checked but not always if will be executed.. So it would be like T(n)= O(n2) +1 // 1 for checking if condition.. (i.e) T(n)= O(n2) because always we take highest order in the quadrant equation.. Am I right?
The return statement is managed by the compiler. The C++ code gets compiled into assembly code. return x; is translated into assembly code as mov x, eax; So it moves the variable x into a register eax, which is the default register for return values. When you write int myNum = F(5); it gets translated into assembly code as mov eax, myNum; The calling function be default looks into the eax register to get the return value from the called function. It assumes that the called function placed the return value into the eax register. That is just how the system is set up. It is part of the GCC Calling Conventions. The compiler automatically does this for you. This is the same as setting up the stack frame of a function, saving the base pointer, moving the stack pointer, and doing other behind the scenes utility work. The compiler may also put into places some other optimizations. In general, the C++ program is portable. While it is good to know what the C++ code is compiled into, in general, it is not part of the algorithm. We do not consider things that the compiler does for the asymptotic time complexity analysis, because that is an implementation-dependent thing. The same C++ program may be compiled into different assembly code depending on: - The CPU hardware architecture (x86_64, ARM, some embedded systems) - The Operating System (Windows, Linux, Mac OS, Android) - The compiler (gcc, clang, Microsoft Compiler) - The optimization settings (-O1, -O2, -O3) We do not know these details when we are writing out the algorithm. We have to look inside the compiled assembly code to find out how the algorithm is implemented.
Here we have calculated the Time Complexity to be of O(n). The iterative implementation is also of O(n) since we iterate over n elements that we need to process. However, while implementing the program for larger inputs, the recursive implementation takes more time. why is it so?
Just to make sure, you didn't count the return as 1 because you can only only go through one block? And it be more expensive(or worst) to go through the else block?
The cost of 1 unit is considered only for those statements that involve some sort of computation. The return statement does not do any computational work, it merely returns a value.
I struggled with this idea too. Basically, he wants to find the amount of operations that happen when we hit our base case. Our base case is hit, when have completed k operations, so basically when n = k. when n = 1 we have done 1 operation, so when n = k we have done k operations, and when have done k operations, we have found the amount of "work" it took to reach out base case. He should have written T(0) + 3k not T(0) + 3n because he is plugging in k. Hope this helped!
In evaluating the time complexity, I want to know how was it okay to generalize the constant (1) in T(n - 1). Shouldn't it stay fixed, why did we generalize it as k.
I'd argue that the recursive equation is not accurate. The equation should be T(n) = n * T(n-1) + c. This leads to the time complexity of O(n) but it is far more accurate since the n is changing over time.
Which approach is this to find the time complexity ? Substitution or recurrence relation or master method .I am usually confused in these three . @mycodeschool
Because i think it's the worst case. You can only go through one block. The if block would be 1 unit and else block is 2 units. So in the worst case calculation, he only includes the else block blocks of time.
But in any case the control goes to "if" or "else" condition and either ine of them must be satisified. So there must be an addition of 1 unit to T(n). But all of this does not matter since we neglect the constant multiplier. ex: In 3n^2,O(n) = n^2 and In 4n^2, O(n)=n^2 as well!!
Time Complexity of any algorithm doesn't depend on whether you do it iteratively or recursively but yes in case of recursion space complexity increases
He is one in a million, best among many, most trusted , I almost gave up on trading then I met him through a friend, Austin is the most trusted trading expert who helped the life of my family and I ,
How were you first able to come up with T(n-2)+6 in the first place. You did an awful job explaining that & it's a very critical piece of information. Same with the reasoning as to every detail on how you came up w/ n-k=0.... Only people who already understand it perfectly (which are the people who don't need to watch this in the first place) are the ones that will understand... Most people don't know how teach that well anyways so I honestly don't fault you too much... Just letting you know that you didn't really help me as much as you may think you did lol
even you passed away you are still making value for others, you are a legend man, rest in peace
He is alive. His friend Harsha is sadly dead. RIP
He is alive. His friend is the one who passed away.
He is alive and Making impactful work in google
@@adilzamal3218
why not he uploading videos now??
@@ManojKumar-ek3fj one of the co-founders died his name is Harsha and he was one of the top competetive programmers in India at that time.
The first two minutes of this video are already so insanely perfect in terms of explaining I cannot thank you enough. Instantly subscribed.
You're the REAL mvp.
totally saved my Algorithms course.
ive been completely lost in this data structures and algorithms class for over a month and this video just cleared up weeks of confusion. thank you!
that was the best and easiest way one can learn. I m fascinated by how easily u r able to create the logic in ur head and implement it. The flow of logic u have is really unique and thanks for sharing the knowledge with us as it is really easy to understand from ur videos. An upgrad faculty of IIIT B has been teaching it with very bad pronunciation and logics and i have been trying to understand this simple calculation from his video since an hour but here only after a single view I am able to understand the approach that i need to make for such calculations. Thanks a lot and may you rest in peace.
I was rather lost on my homework. Within the first 3 minutes of this video everything made sense. Thank you so much!
Hi Amar,
If you see, if (n == 0) statement will always be executed.. .. return may not be executed always. That's why adding up 1 unit for the if condition. :)
Man where are you !!
@@kedarpednekar9582 he is not with us anymore, RIP
@@mayankbisht2916 oh 😶
@Vivek Sharma It is dead now, last video was uploaded 4 yrs. ago.
Your tutorials are like treasures for learners.. don't know why you stopped making tuts... but please make tutorial series on system design
Look at first comment bro
I was searching for this simple stuff for 3 days. Thank you
T(0) should be 2 not 1 because in the previous videos,it was told to consider the return operation as 1 unit too.
SWAPAN JAIN The answer doesnt change,but still..
that was for a model machine you can have your own model machine which may take 2 units per operation or anything as long as its a constant
Interesting point.
Hi,
As per your previous tutorial, you mentioned like whenever there exist and conditional statement we should take up the worst case scenario and we should not add up the time complexities of both conditions because its either-or right. So in that case the above complexity should be calculated as
T(n) = T(n-1) + 2 // 2 is constant time in worst case scenario
T(n) = T(n-2) + 4
(i.e) T(n-k) + 2k
when n-k =0, k=n => T(n)= T(0)+2n = 2n => O(n)
Yes, you are right bro...I had same thought.
Thank you for your legacy, the world will miss you
it look like old video, but very interesting, uploaded when l was in class 4 and now watching it in third year university degree level, how interesting this video is
wow, keep it up bro
your videos are the G.O.A.T
man, why this video isnt in the compilation of the time analysis? btw...the important thing I wanted to say is GJ! TY VERY MUCH!!! you are very clear and I understand all that tstuff ;D ty
answer would change if we consider return operation as 1
and the exp=t(n)+4
also t(0)=2;
so ans should be 4n+2
Why can T(n-1)+3 be written as T(n-2)+6 ... and eventually T(n-k)+3k?
For anyone else wondering this is just badly written index notation.
The (n-1)+3, (n-2)+6.. (n-k)+3k are the index positions.
It is not T multiplied by (n-1)+3 etc
+Chris Auret thank you for your link! This Guy is an idiot not explaining
+Chris Auret
Replace n by (n-1) in T(n)
T(n-1)=T(n-2)+3
Now put this in T(n)
T(n)=(T(n-2)+3)+3=T(n-2)+6
The guy assumes that you understand recursion.
Thanks.
Sir in this video you are taking T(n)=T(n-k)+3k but According to the first equation T(n)=T(n-1)+3 the last equation must be T(n-(k-1))=T(n-k)+3k in the factorial recursion example
An expression for T(n) can also be found using unilateral Z transform in case the equation becomes complex.
Can you elaborate?
I think its wrong .... You said in the previous leson that we do not add complexities in conditional statement , rather we take the max of the conditional statements.
At 2:10 although the value is correct i.e. t(n)=t(n-1)+3 but one 1 in the three comes from return statement not from the if statement.
In that video, you directly took O(n2) regardless of if statement execution.. So little confused. So even in that case if condition will be checked but not always if will be executed.. So it would be like T(n)= O(n2) +1 // 1 for checking if condition.. (i.e) T(n)= O(n2) because always we take highest order in the quadrant equation.. Am I right?
i learnt this in 10 minutes as compared 120 minutes of my teacher trying to teach me
So true 😂
True brother
Thank you!!!!! Ugh I needed this exact explanation about space complexity..!!!!
Excellent explanation and teaching methods.. thanks a million..
RIP sir humblefool. thank you for your amazing contribution
Excellent explanation! Also, this uses O(1) Auxillary Space right?
Theta n
Got it.. Thanx for the clarification.. It's helpful.. Wonderful effort.. Keep going..
How did you clarify it ?
Why are you not considering return statement as one unit.....
The return statement is managed by the compiler. The C++ code gets compiled into assembly code.
return x; is translated into assembly code as mov x, eax; So it moves the variable x into a register eax, which is the default register for return values. When you write int myNum = F(5); it gets translated into assembly code as mov eax, myNum;
The calling function be default looks into the eax register to get the return value from the called function. It assumes that the called function placed the return value into the eax register. That is just how the system is set up. It is part of the GCC Calling Conventions. The compiler automatically does this for you. This is the same as setting up the stack frame of a function, saving the base pointer, moving the stack pointer, and doing other behind the scenes utility work. The compiler may also put into places some other optimizations.
In general, the C++ program is portable. While it is good to know what the C++ code is compiled into, in general, it is not part of the algorithm. We do not consider things that the compiler does for the asymptotic time complexity analysis, because that is an implementation-dependent thing.
The same C++ program may be compiled into different assembly code depending on:
- The CPU hardware architecture (x86_64, ARM, some embedded systems)
- The Operating System (Windows, Linux, Mac OS, Android)
- The compiler (gcc, clang, Microsoft Compiler)
- The optimization settings (-O1, -O2, -O3)
We do not know these details when we are writing out the algorithm. We have to look inside the compiled assembly code to find out how the algorithm is implemented.
im lost at 2:17, how does it go from t(n-1) + 3 => t(n-2) + 6, then t(n-3) +9?
Apply the same T(n) equation to T(n-1) i.e put n-1 instead of n in the equation
Nicely explained, Thank you.
Aren't we supposed to consider unit time for return statements too. If we consider it, T(n) will be equal to T(n-1)+5 in the first program right ??
Here we have calculated the Time Complexity to be of O(n). The iterative implementation is also of O(n) since we iterate over n elements that we need to process. However, while implementing the program for larger inputs, the recursive implementation takes more time. why is it so?
very good video thanks mister !
Just to make sure, you didn't count the return as 1 because you can only only go through one block? And it be more expensive(or worst) to go through the else block?
The cost of 1 unit is considered only for those statements that involve some sort of computation. The return statement does not do any computational work, it merely returns a value.
Can someone explain how (n-k) becomes equal to 0?
Zabby nemo n-k=0 is used to make it base condition i.e T(0)
I struggled with this idea too. Basically, he wants to find the amount of operations that happen when we hit our base case. Our base case is hit, when have completed k operations, so basically when n = k. when n = 1 we have done 1 operation, so when n = k we have done k operations, and when have done k operations, we have found the amount of "work" it took to reach out base case. He should have written T(0) + 3k not T(0) + 3n because he is plugging in k. Hope this helped!
What if , we had more than 1 line of code within the if block ?
Will it still be 1 unit of computation for the if block (comparison) ?!
Plz, can you explain how use log to compute complexity time for any example !!
Log basically just means if you double the size of the input, you only need one marginal time input to account for that increase in size.
He did a video about this. Here's the link to it: ua-cam.com/video/PFd5s0bHgAQ/v-deo.html
In evaluating the time complexity, I want to know how was it okay to generalize the constant (1) in T(n - 1). Shouldn't it stay fixed, why did we generalize it as k.
Is the space complexity only depending on the function call? What if we don't have a recursion method
Is the function call an operation? so it is T(n) = T(n-1) + 4 ?
What method did you use to calculate time complexity? Was it substitution method?
yes bro
why there is no time assigned for returning value...he did assigned a value in a previous video in time complex analysis section
yeah because its inside the t(n-1)..
can you make a video on
fact(n)
{
for i=1 to n
fact=fact*i;
return fact;
}
how many steps are there?
time complexity?
humblefool the LEGEND
I'd argue that the recursive equation is not accurate. The equation should be T(n) = n * T(n-1) + c. This leads to the time complexity of O(n) but it is far more accurate since the n is changing over time.
Assignment or Return function has 1 unit as said in previous videos why are we not taking that ??
1 is insignificant compared to n anyway
what is the best time complexity of recursive factorial?
Hello has anyone knows where I can find the other videos? I really need this. Please thank you.
thank you so much.
Which approach is this to find the time complexity ? Substitution or recurrence relation or master method .I am usually confused in these three . @mycodeschool
Why isn’t F(0) in the memory? I don’t get it.
in the statement T(n)=T(n-1)+3,why is it T(n-1)??
Shouldn't you be adding one more unit time for T(0)?
One for "if(n == 0)" and another one for "return 1"?
I think T(n) should be 2, not 1.
Because i think it's the worst case. You can only go through one block. The if block would be 1 unit and else block is 2 units. So in the worst case calculation, he only includes the else block blocks of time.
But in any case the control goes to "if" or "else" condition and either ine of them must be satisified. So there must be an addition of 1 unit to T(n). But all of this does not matter since we neglect the constant multiplier. ex: In 3n^2,O(n) = n^2 and In 4n^2, O(n)=n^2 as well!!
why didnt include the one unit time of return 1 statement
?
Don't know if it would help but see my comment near the top.
how directly n-k=0 is done (why it is equal to 0).........I can't understand that.
Very helpful.
Thanks. Great tutorial.
❤️thanks
wonderful work....
Does recursion reduce time complexity and increases space complexity or its the inverse of it?
Please HElp URGEnt
Time Complexity of any algorithm doesn't depend on whether you do it iteratively or recursively but yes in case of recursion space complexity increases
i think it will be T(n)=T(n-1)+2 bcoz there if and else there
why is T(n) = t(n-1) and not t(n)??
why not T(n)+2 ?
Nice one.. thanks..
nice video, well explained but the volume of the audio is very low
great.
thanks a lot!!
Thanks!
He is one in a million, best among many, most trusted , I almost gave up on trading then I met him through a friend, Austin is the most trusted trading expert who helped the life of my family and I ,
-+/1/5/3/0/4/2/8/5/8/70/W/h/a/t/s/A/p/p/< With> /
A/U/s/t/In/
I want to only know definition of complexcity and type of complexcity in toc
great one ;)
Is that memory table the stack in the computer's memory?
Audio is very low
helpfull
I hate computer engineering so much
I'm a simple man I see Recursive fn(); I Panic !
Nixooo
Sound quality is not god
Wiiiiiider
bhai thoda tez bol liya kr
How were you first able to come up with T(n-2)+6 in the first place. You did an awful job explaining that & it's a very critical piece of information. Same with the reasoning as to every detail on how you came up w/ n-k=0.... Only people who already understand it perfectly (which are the people who don't need to watch this in the first place) are the ones that will understand... Most people don't know how teach that well anyways so I honestly don't fault you too much... Just letting you know that you didn't really help me as much as you may think you did lol