- 16 minutes ago
Transcript
00:00Next we will talk about recursive function
00:01This is my power function
00:03Power function means this function
00:04I calculate my power
00:06Power means a to the power n
00:09We have a power function in the math library
00:12We use math.pow
00:13a to the power n
00:14We use this statement
00:17I have written this function
00:20What is a to the power function
00:21A to the power n
00:22What is a to the power n
00:25What is a to the power n
00:29I calculate a to the power n-1
00:31Then I multiply it from a
00:34My recursion is like
00:35What I did first?
00:37I called f of a to the power n
00:38What did it?
00:40It called f of a to the power n-1
00:43This function calculates a to the power n
00:46This function calculates a to the power n-1
00:48I will multiply it from this
00:50With this, I will multiply it
00:52I know that when a multiply
00:53a to the power n-1
00:54This is very basic math
00:58This function will call
00:59This function will call
01:00A to the power n by 2
01:03And here it will multiply
01:04This will also be a to the power n-2
01:07Now who will call it?
01:09It will call itself for calculation of a to the power n-3
01:12This will also be a to the power n-3
01:15This will also be a to the power n-3
01:16And what will calculate a to the power n-3
01:17And this will be called
01:19When will it be called?
01:20What is the base case?
01:22The base case is for n is equal to 0
01:24I know that for n is equal to 0
01:27If a value is something
01:28If it comes to the power n-2
01:29If it comes to the power n-2
01:32What is the base case?
01:33It is equal to 1
01:34So I have returned 1
01:37Now the base case is returned
01:39Here the base case will be hit
01:41I am returning
01:43For f of a to the power n-3
01:46So I will return my value 1
01:49So I will have some levels
01:50In the recursion
01:51In which my recursion is calling
01:53And calling
01:54For this
01:55Time complexity
01:56This is my linear case
01:58In which I will call myself
02:00Every time with minus 1
02:01So in the linear case
02:02What was the work done?
02:05My number of calls
02:07Multiplied by
02:08Time in
02:11Each call
02:14This is another
02:14Itsuntu
02:14The number of calls
02:15My number of calls
02:16Since
02:16I have to take from n to minus 1
02:18And three to соглас
02:23First
02:23I will 2
02:24I will kill upś
02:34Whichever
02:35Time between
02:36this is also constant time, that means the answer you have already,
02:40think that the answer is x, if I want to multiply it from a,
02:44this is constant operations, it will also be constant time,
02:47so here it will be constant time, so my work will be done,
02:51n into k, that will be bigger of n,
02:56this constant will be cut here, how much space will come,
02:59how many calls will come, how many calls will be multiplied by every call,
03:04so what can I say in my stack, what will happen,
03:07one after one after one after one,
03:09every level will be called,
03:11here it will be called for a by n,
03:13here it will be called for a, n-1,
03:15for a, n-2,
03:17for a, n-3,
03:19this way will be called for a of 0,
03:21so how many levels will come,
03:23n levels, so in my recursion,
03:25how many levels will become in stack calls,
03:27I will become n levels in space complexity,
03:29and how many levels will become in every level,
03:32every level will be constant space,
03:33because I have one function call,
03:35there is no extra space,
03:36there is no extra variables,
03:38so this is my constant space complexity,
03:40so space complexity,
03:42constant for each level,
03:44for each level,
03:46and this is my total levels,
03:48so why do we use total levels,
03:50because in recursion,
03:51space complexity,
03:51not only variables,
03:53space complexity,
03:54we also tell our stack calls,
03:56so that's why my space complexity,
03:58that will be big of n,
04:00so my space complexity,
04:01is big of n,
04:02and my time complexity,
04:04is big of n,
04:05so we have calculated power,
04:07now we can optimize this power function,
04:09we can optimize this power function,
04:11in terms of recursion,
04:13how do we optimize recursion,
04:14what we can do here,
04:16what we have used here,
04:18I have calculated a to the power n,
04:21from a to the power n-1,
04:23then a to the power n-1,
04:25from a to the power n-1,
04:26from a to the power n-2,
04:27then a to the power n-2,
04:29from a to the power n-2,
04:30from a multiplied by a to the power n-3,
04:33from a to the power n-3,
04:33I have calculated this power,
04:34but power calculate,
04:36is another separate formula,
04:37or another separate method,
04:39how?
04:40if I have a to the power n,
04:42I have to calculate,
04:42then I can write it,
04:44a to the power n by 2,
04:45multiplied by a to the power n by 2
04:47what do I do every time?
04:48I half this power
04:49I will do this half power
04:50so I can understand
04:52that my time complexity is
04:54n to log in terms
04:56because when I start halfing things
04:59I should have to stop
05:01that my time complexity
05:03should be related to log in
05:05most of the cases
05:06this will happen for an even case
05:08that is if I have to calculate
05:10a to the power 6
05:12then this can be written as
05:14a to the power 3 multiplied by a to the power 3
05:16what will happen in the odd case?
05:18for the odd case
05:18i can write a to the power 3
05:22into a to the power 3
05:23multiplied by a
05:25so what can i say?
05:26this is my half power
05:27this is also my half power
05:29half power square i have removed
05:32and multiplied it with a
05:33this is for my odd case
05:36now i am just taking an even case
05:37we can write an even case
05:38in implementation we can write an odd case
05:39so what will happen?
05:41this will happen
05:42how will i write a to the power?
05:43then what will i write it with a to the power in the powerzon we can write on the power
05:46of a to the power and multiplied n by four
05:48so this led us to divide this
05:51it will then divide it with a made of power and the other mean
05:55so with half power I will multiply also by a half power
05:58if I will summarize this
06:00second thing
06:01what is the second way
06:03that I have to remove a to the power n
06:04what do I do every time
06:05I will remove a to the power n by 2
06:06and remove a to the power n by 2
06:09if my number is odd
06:11then I will multiply a too
06:14what do I do
06:15remove a to the power n by 4
06:16and remove a to the power n by 4
06:19if this value is even
06:20then it is odd
06:21then what do I need to do
06:24so this is my parallel
06:26or my second way
06:27to calculate the power function
06:29and if I write a code
06:31then I will analyze the time complexity
06:32that code
06:32I will analyze the time complexity