00:00The next question we will solve is sum of n.
00:03How do we calculate sum of n integers?
00:05We have already written a function when we were studying Recurgeon Basics.
00:09We have a function called sum, which is n.
00:12And what was the first time?
00:14We had call to calculate n-1.
00:17So this was my faith step.
00:20We had call to remove n-1.
00:23And when I add n numbers,
00:27the sum of n numbers will come.
00:29So what was the function called?
00:32I add n to n-1.
00:39The base case was that if n is 0,
00:42the sum of n was equal to 0.
00:47If the value of n is equal to 0,
00:49I could write 1 in the base case.
00:51So this is a proper base case for natural numbers.
00:54We have taken whole numbers.
00:56So both of them are okay.
00:58Let's talk about logic.
00:59How do we start with time complexity and space complexity?
01:02First of all, let's see the call stack.
01:05Which way is the call stack?
01:06It will be something like this.
01:08First of all,
01:08it will be called for my fn.
01:10What will I do?
01:11Fn will call for fn-1.
01:13What will I do?
01:14Fn-2 will call for fn-2.
01:16And this will be called up to above.
01:17Until I finally reach f of 0.
01:20I have to visualize this in a tricky form.
01:22I take an example of n is equal to 4.
01:25So what will happen?
01:26F4 will call for f3.
01:29What will I do?
01:30We will add 4.
01:31This will call for f2.
01:33What will I do?
01:33F2 will add 3.
01:34This will call for f1.
01:36F1 will add 2.
01:37This will call for f0.
01:39And this will add 1.
01:40So in this way,
01:41a factorial call will come.
01:43What will I do?
01:45I want to calculate some.
01:46So here,
01:47we have to do very similar things.
01:49First of all,
01:49let's talk about time complexity.
01:51How do we get out of time complexity?
01:53Time complexity will be,
01:54what is my work done?
01:56How will work done?
01:57Number of calls
01:59multiplied by
02:01work in each call.
02:04Number of calls
02:05How will total calls come to me?
02:07If the first call is for n,
02:10then the next call is for n-1.
02:11The next call is for n-2.
02:13The next call is for n-2.
02:13In this way,
02:14there will be calls until I reach 0.
02:16So if we get out of n,
02:18we get out of 0.
02:19So how will total calls come to me?
02:20Obviously,
02:21n calls.
02:22And work in each call,
02:24how many calls are working in each call?
02:26If I take an example of a call,
02:27this is my constant work.
02:30This is my constant work.
02:32Where is the real work?
02:34The real work is to call this recursion.
02:36If I take a single call,
02:38this recursion call is removed from here.
02:40So this work is also constant.
02:42This work is also constant.
02:43So what can I say?
02:44Every call,
02:45what I'm doing is that is equal to a constant k.
02:48So what will total time complexity come to me?
02:50This will come to big of n k.
02:52Which will be big of n.
02:54Because this constant will be removed.
02:56Now what will happen to me?
02:57To do space complexity,
02:57what is happening?
02:58Space complexity was,
03:00my depth multiplied by memory
03:05in each level.
03:07Each level means,
03:08which is one level
03:09in this one level,
03:10and this one level in this one level.
03:14So I can say that this one level,
03:16which is my only call,
03:18I have called it once again,
03:20or I take this one and this one.
03:22these are the same things
03:24or I can see directly in my function
03:25how many memory is occupied
03:27or I can see in my call stack
03:28in my single call
03:31how many memory is occupied
03:32or I can see in my recursion tree
03:34how many memory is occupied
03:36this is equal to this is equal to this
03:39or single level is equal to single call frame
03:42is equal to single level of recursion
03:46so if I talk about depth
03:47where will recursion
03:49we know before n
03:51then n-1
03:52then n-2
03:53then n-3
03:54if I want to visualize this in single line
03:57here first value is n
03:59then n-1 then n-2
04:01then n-3
04:03where is it going to 0
04:04so how much depth will be here
04:06that will be equal to
04:08memory in each level
04:12I will talk about every level
04:13how many extra variables stored in this level
04:15there is no extra variable stored
04:16so what is it doing?
04:17I am taking constant memory
04:19so here I can call it
04:21constant
04:22but constant
04:23ignore it
04:23that will be big of n
04:27so I will summarize these both
04:28in summary
04:30my time complexity
04:31will be sum of n
04:33that will be big of n
04:35and space complexity
04:36will be big of n
04:38give it up
04:38as either
04:38maybe