Time and space complexity analysis of recursive programs - using factorial

[@danhle7999]

even you passed away you are still making value for others, you are a legend man, rest in peace

[@sahilbabbar8859]

He is alive. His friend Harsha is sadly dead. RIP

[@ShawnDypxz]

He is alive. His friend is the one who passed away.

[@adilzamal3218]

He is alive and Making impactful work in google

[@ManojKumar-ek3fj]

@@adilzamal3218 why not he uploading videos now??

[@vigneshsenthil7980]

@@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.

[@IAmNigHtMaReTR]

You're the REAL mvp. totally saved my Algorithms course.

[@taylor-bn8ll]

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!

[@OneLordeAnimeClips]

The first two minutes of this video are already so insanely perfect in terms of explaining I cannot thank you enough. Instantly subscribed.

[@samarthmohanty6755]

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.

[@shado5482]

I was rather lost on my homework. Within the first 3 minutes of this video everything made sense. Thank you so much!

[@mycodeschool]

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. :)

[@kedarpednekar9582]

Man where are you !!

[@mayankbisht2916]

@@kedarpednekar9582 he is not with us anymore, RIP

[@kedarpednekar9582]

@@mayankbisht2916 oh 😶

[@amritaanshnarain7524]

@Vivek Sharma It is dead now, last video was uploaded 4 yrs. ago.

[@sethubalaji9141]

I was searching for this simple stuff for 3 days. Thank you

[@sase1017]

Thank you for your legacy, the world will miss you

[@Shikschauhan]

Your tutorials are like treasures for learners.. don't know why you stopped making tuts... but please make tutorial series on system design

[@chandragirivishnuvardhan7654]

Look at first comment bro

[@vortyx090]

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

[@AmarNathami1906]

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)

[@basavarajrajur7720]

Yes, you are right bro...I had same thought.

[@swapanjain892]

T(0) should be 2 not 1 because in the previous videos,it was told to consider the return operation as 1 unit too.

[@swapanjain892]

SWAPAN JAIN The answer doesnt change,but still..

[@AkshayKumar-dz5ts]

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

[@NeelSandellISAWESOME]

Interesting point.

[@sindhiyar]

your videos are the G.O.A.T

[@gouravm4986]

RIP sir humblefool. thank you for your amazing contribution

[@spobob88]

Thank you!!!!! Ugh I needed this exact explanation about space complexity..!!!!

[@chiengdorkcy4851]

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

[@TheGokhansimsek35]

Excellent explanation and teaching methods.. thanks a million..

[@chrisauret3785]

Why can T(n-1)+3 be written as T(n-2)+6 ... and eventually T(n-k)+3k?

[@chrisauret3785]

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

[@AhmedThaking]

+Chris Auret thank you for your link! This Guy is an idiot not explaining

[@AnkitaSharmaHoran]

+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

[@pixel8547]

The guy assumes that you understand recursion.

[@soumyadeepmukhopadhyay475]

Thanks.

[@himanshunahak5105]

i learnt this in 10 minutes as compared 120 minutes of my teacher trying to teach me

[@ayeshachaudhury7504]

So true 😂

[@anubhavsingh9049]

True brother

[@swagatzeher]

Nicely explained, Thank you.

[@aashish1502]

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

[@vivekupadhyay6663]

An expression for T(n) can also be found using unilateral Z transform in case the equation becomes complex.

[@NeelSandellISAWESOME]

Can you elaborate?

[@DharokWretched]

Excellent explanation! Also, this uses O(1) Auxillary Space right?

[@kavirajpandey8826]

Theta n

[@roohuop]

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?

[@himanshukesarwani7446]

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

[@AmarNathami1906]

Got it.. Thanx for the clarification.. It's helpful.. Wonderful effort.. Keep going..

[@gowthams6093]

How did you clarify it ?

[@RicsDev]

very good video thanks mister !

[@ahmedzak7475]

Plz, can you explain how use log to compute complexity time for any example !!

[@NeelSandellISAWESOME]

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.

[@ZerOv07]

He did a video about this. Here's the link to it: kzbin.info/www/bejne/hnfHZqZml62ad7M

[@samsons8279]

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) ?!

[@AmarNathami1906]

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?

[@likithasahukari457]

Why are you not considering return statement as one unit.....

[@konstantinrebrov675]

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.

[@rathodkirthi1108]

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 ??

[@mustafaalisaba5168]

Is the function call an operation? so it is T(n) = T(n-1) + 4 ?

[@birendrakumarsingh2148]

humblefool the LEGEND

[@huydang6059]

Is the space complexity only depending on the function call? What if we don't have a recursion method

[@stevefox7418]

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.

[@heyyyyyworld]

Can someone explain how (n-k) becomes equal to 0?

[@ArshadAli_]

Zabby nemo n-k=0 is used to make it base condition i.e T(0)

[@NeelSandellISAWESOME]

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!

[@MohanaKrishnaVH]

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?

[@ryeonnaderi6731]

im lost at 2:17, how does it go from t(n-1) + 3 => t(n-2) + 6, then t(n-3) +9?

[@mtariquegauri]

Apply the same T(n) equation to T(n-1) i.e put n-1 instead of n in the equation

[@mdsaif4696]

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.

[@kid_kulafu_1727]

Hello has anyone knows where I can find the other videos? I really need this. Please thank you.

[@GuitaristVoyage]

Which approach is this to find the time complexity ? Substitution or recurrence relation or master method .I am usually confused in these three . @mycodeschool

[@sanafatima1820]

what is the best time complexity of recursive factorial?

[@J0N36O]

What method did you use to calculate time complexity? Was it substitution method?

[@Aryan-wv6qe]

yes bro

[@lasredchris]

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?

[@PoojithJainK]

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.

[@jaimin__sagar]

how directly n-k=0 is done (why it is equal to 0).........I can't understand that.

[@ivyzheng8681]

Why isn’t F(0) in the memory? I don’t get it.

[@shuvshaw9594]

Very helpful.

[@Littleangel1306]

wonderful work....

[@kumarabhijeet5877]

in the statement T(n)=T(n-1)+3,why is it T(n-1)??

[@ThePratikp]

Thanks. Great tutorial.

[@god-speed03]

why there is no time assigned for returning value...he did assigned a value in a previous video in time complex analysis section

[@god-speed03]

yeah because its inside the t(n-1)..

[@rore3801]

thank you so much.

[@abhrajyotikirtania2275]

Nice one.. thanks..

[@gowthams6093]

Assignment or Return function has 1 unit as said in previous videos why are we not taking that ??

[@h.m.chuang0224]

1 is insignificant compared to n anyway

[@kollikishore3567]

why didnt include the one unit time of return 1 statement ?

[@lasredchris]

Don't know if it would help but see my comment near the top.

[@vishaldeepak2538]

nice video, well explained but the volume of the audio is very low

[@asthajindal6463]

Does recursion reduce time complexity and increases space complexity or its the inverse of it? Please HElp URGEnt

[@akhileshswaroopxisrnnadbt3669]

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

[@vanillarootbeer]

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.

[@lasredchris]

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.

[@SaiKrishna-mo5kv]

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!!

[@rishigupta6515]

i think it will be T(n)=T(n-1)+2 bcoz there if and else there

[@RaselAhmed-ix5ee]

why is T(n) = t(n-1) and not t(n)??

[@hkorany12]

why not T(n)+2 ?

[@Nylon-xj9ml]

I hate computer engineering so much

[@rezaes8848]

❤️thanks

[@bodhibriar9683]

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 ,

[@bodhibriar9683]

-+/1/5/3/0/4/2/8/5/8/70/W/h/a/t/s/A/p/p/< With> / A/U/s/t/In/

[@nuriffah7539]

thanks a lot!!

[@medic0re]

great one ;)

[@lasredchris]

Is that memory table the stack in the computer's memory?

[@nizki121]

Thanks!

[@bhavnajain4703]

I want to only know definition of complexcity and type of complexcity in toc

[@AnonymousCoder7]

I'm a simple man I see Recursive fn(); I Panic !

[@sssumeet]

great.

[@adeeqasubahat7070]

helpfull

[@prabudh6713]

Audio is very low

[@SACHINSINGH-re5ft]

Nixooo

[@abhishekwadhawan5381]

bhai thoda tez bol liya kr

[@khodis2002]

Wiiiiiider

[@r060zeeshankhan9]

Sound quality is not god

[@david-tracy]

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