Time and space complexity analysis of recursive programs - using factorial

See complete series on recursion here
We will learn how to analyze the time and space complexity of recursive programs using factorial problem as example.

Prerequisite: Understanding of the concept of recursion in algorithm design.

[danhle]

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

[OneLordeAnimeClips]

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

[IAmNigHtMaReTR]

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

[samarthmohanty]

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.

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

[taylor-bnll]

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!

[shado]

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

[vortyx]

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

[swapanjain]

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

[AmarNathami]

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)

[Shikschauhan]

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

[sethubalaji]

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

[chiengdorkcy]

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

[sase]

Thank you for your legacy, the world will miss you

[TheGokhansimsek]

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

[chrisauret]

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

[aashish]

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

[spobob]

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

[gouravm]

RIP sir humblefool. thank you for your amazing contribution

[DharokWretched]

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