• 15 minutes ago
Transcript
00:00Now let's analyze our power function 2
00:02Now we have discussed the method that we have discussed in half
00:07We are discussing this method in this method
00:10We have written a recursive function in power 2
00:13This function is implementing the same logic
00:15I have my parameters A and my parameters N
00:19What is my base case?
00:21When the value is 0, I have a base case
00:23My power is 0
00:25If a power is 0, it is always 1
00:27So I will return 1 here
00:30Then what I am doing?
00:31Every time I calculate a to the power n by 2
00:35So I have called a power function for a and for n by 2
00:39Then what I have done?
00:40I have calculated the power of a to the power n by 2
00:44So I have called a and n by 2
00:46So what I am doing?
00:48Here I will have a to the power n by 2
00:50Here I will have a to the power n by 2
00:53And I will store this in this variable
00:55Which is called half power square
00:56So a to the power n by 2 multiplied by a to the power n by 2
01:01I know this will become a to the power n by 2 plus n by 2
01:04This is eventually going to become a to the power n
01:07Now if my a is odd
01:09So what happens in this case?
01:10What happens in this case?
01:10A to the power 7
01:11What happens in this case?
01:12A to the power 3 multiplied by a to the power 3
01:15So only I have a to the power 6
01:16So I need to multiply a more a to the power n by 2
01:19So when my value is odd
01:21What do I do?
01:22I will multiply this value from a to the power n by 2
01:33So for a to the power 7
01:34So for a to the power n by 2
01:35I have a square and a square
01:37I have multiplied by a to the power 4
01:39So I need to run this value from a to the power 4
01:40In this case I need to run this value
01:42This is my logic
01:43Finally I will return my half power square
01:45In this function
01:47Now I have implemented this logic
01:48In this recursive function
01:49What is the time complexity?
01:50What will be the time complexity?
01:51For time complexity
01:53I will try to intuitively solve this
01:55I will try to do this
01:57What did I do every time?
01:58A to the power n
01:58I put this function
02:01F of a to the power n
02:02What did I do?
02:04F of a to the power n by 2
02:06And the other call
02:07It put a call for a to the power n by 2
02:10What did I do?
02:11F of a to the power n by 2
02:12Call n to the power 4
02:16And another call
02:17It put f of n to the power 4
02:19And one call to the power n by 4
02:22And for a call
02:23And f of a to the power n by 4
02:26From this point
02:27Calls are still waiting
02:29How will the calls find?
02:31Until I come to last
02:32Where will I reach to the power n
02:33is equal to 0
02:34So this will also stay to f of 0
02:36This will also stay to f of 0
02:37This will also stay to f of 0
02:38This will also stay to f of 1, 0
02:39This will also stay to f of a to the power n
02:41This will also stay to f of a
02:42So how many levels did I do?
02:44What are the levels of total?
02:45What do I do every time?
02:46I divide by n
02:47N divided by 2, then N divided by 2, then N divided by 4, here N divided by 8.
02:55In this way, I will get N to divide by 0.
02:58So if these are my x levels, I will derive this again.
03:01If these are my x levels, then N divided by 0, N divided by 2 to the power 0, N
03:07divided by 2 to the power 1, N divided by 2 to the power 2,
03:14so where will I come to the last level?
03:17So what can I say? N divided by 2 to the power x is equal to 1.
03:22When I reach the last level, it will be 1 or 0.
03:25In this case, I will take 1.
03:26Because if I do 0, then everything is going to be 0.
03:30So I will take 1, so I will take 1 to the last level.
03:33When I divide 1 from 2, because it is an integer variable, then it will be 0 in Java.
03:40So I will end it on 1.
03:41So I can say that the value of x will equal to N, or my x will equal to log
03:47N based 2.
03:48So how many levels are here?
03:50My log N levels are here.
03:51So how many levels are my log N levels?
03:53How many levels are my log N levels?
03:53How many levels are my log N levels?
03:55Now I have put the whole recursion here, which are log N levels,
03:58I can write the same recursion in this recursion.
04:02Let's write the recurrence.
04:03How will recurrence come?
04:04If my time complexity is T of N,
04:07So what can I say?
04:09This will be T of N by 2.
04:11That means the power is half.
04:12Plus T of N by 2.
04:14Plus some constant work.
04:16That means this part is constant work.
04:19This part is constant work.
04:20This part is constant work.
04:22This part is constant work.
04:23So within one call,
04:24this complexity will count.
04:26The rest of the part is constant.
04:28So for this recurrence relation,
04:30I'm going to solve it once again.
04:31So if my total time,
04:33which I calculate a to the power N,
04:35that is equal to T of N.
04:37So what can I say?
04:38This is 2 times T of N by 2.
04:41Which every time the power is half.
04:42Plus some constant.
04:44Now from here,
04:45T of N by 2.
04:47What can I say?
04:48This is 2 times T of N by 4.
04:51Plus some constant.
04:53Now I have to cut this term from this term.
04:54I have to cut this term.
04:55Why did I use this recurrence?
04:57Because what do I do?
04:59Every time I use divide and conquer.
05:01How did I divide my problem?
05:03I have to divide my problem.
05:04I have to divide my problem.
05:05I had to calculate a to the power N.
05:07So first calculate a to the power N by 2.
05:09And calculate a to the power N by 2.
05:11And calculate a to the power N by 2.
05:12I have to calculate a small part.
05:12So I have to make a big solution.
05:14So that's why I use recurrence.
05:17I have to cut this term.
05:18So I have to cut this term here.
05:19So I have to multiply by 2.
05:20So I will do this whole equation here.
05:21I will multiply by 2.
05:23As I have multiplied by 2.
05:24As I have multiplied by 2.
05:24Here is 2.
05:25So this is multiplied by 2.
05:27And here is multiplied by 2.
05:29Next what I will write.
05:30T of N by 4 is equal to 2 times T of N by 8.
05:35Plus my constant K.
05:37Now I have to cut this term.
05:39So I will multiply by 4.
05:41So this is 4.
05:42This will become 8.
05:43And this will become 4.
05:46Next what I can write.
05:48T of N by 8 is equal to 2 times T of N by 16.
05:52Plus some constant K.
05:54Now I have to cut this term from this term.
05:56So I will multiply by 8.
05:59Here will be 8.
06:01This will become 16.
06:02Here will be 8.
06:04So I will multiply by 8.
06:06This will be equal to 1.
06:08This will become 2 times T of 0.
06:11I will call plus K.
06:14And I know T of 0.
06:16What is my base case?
06:18T of 0 is a base case.
06:19And its time complexity is constant time complexity.
06:22Because we saw that in our recursion
06:25When my value is 0,
06:27I will return simply 1 to 1.
06:29This takes constant time.
06:31So I can replace this T of 0.
06:36Let's say I will replace T of 0 with some constant.
06:39I will call it K2.
06:42Now we start to cut the terms.
06:44This will cancel from this term.
06:46This term will cancel from this term.
06:48This term will cancel from this term.
06:49This term will cancel from this term.
06:51And any term will cancel from this term.
06:54What will I have here?
06:56Here I have T of n.
06:58What will I have here?
07:00From this second line.
07:01Here I have 2 into K2.
07:04I can say this is my constant K3.
07:07I will write it as constant K3.
07:11Plus I have to add the rest of the constants.
07:14What will happen?
07:15This is K.
07:16K into 2 to the bar 0.
07:18This is K into 2 to the bar 1.
07:20This is K into 2 to the bar 2.
07:23This is K into 2 to the bar 3.
07:25This will also be K into 2 to the bar 3.
07:29This will also be K into 2 to the bar x.
07:31How many levels?
07:31I don't know how many log n levels are.
07:34I won't do this for 4 times.
07:36Because now we should have to understand intuitively.
07:39We can do it ourselves.
07:39We can do n by 2.
07:41Then n by 4.
07:42Then n by 4.
07:42Then n by 8.
07:43Then n by 16.
07:44Then n by 16.
07:45Then n by 1.
07:46Then divide by 2.
07:47How many times will come?
07:48This will come in my log n times.
07:51What will happen here?
07:52This will be K into 2 to the bar log n.
07:56If I add all these subs.
07:58I can take K into common.
08:00What will happen?
08:002 to the bar 0.
08:012 to the bar 1.
08:022 to the bar 2.
08:032 to the bar 3.
08:052 to the bar log n.
08:07And this is log n.
08:09I can say height of my recursion tree.
08:11So I will take here.
08:12T of n is equal to some constant value.
08:15Plus some constant multiplied by.
08:16This is my geometric progression.
08:18What will come to this answer?
08:192 multiplied by 2.
08:21Because it is a common number.
08:23Every time there is multiplication.
08:252 to the bar.
08:27How many times?
08:28Log n times.
08:29Minus 1 divided by 2 minus 1.
08:31If I solve this, it will come to this.
08:34This will be equal to some constant K.
08:40K into 2 to the bar log n.
08:42Plus 1.
08:43Minus 2 divided by 1.
08:46Now I will remove all the values.
08:49So from here.
08:51This will be equal to T of n.
08:55Is my constant.
08:57If I multiply here too.
08:58This will be K into 2 to the bar.
09:02Log n.
09:03Plus 1.
09:05Minus 2K.
09:19Log n.
09:32Base 2.
09:34Log n.
09:35Base 2.
09:36Mathematically.
09:46Log n.
09:49Log n.
10:00Log n.
10:02Log n.
10:02I then have calculated.
10:03I have calculated in n time.
10:06I have calculated in n time to this.
10:09That is what we have observed.
10:12In this same function, we have another special thing.
10:16This function is not fully optimized.
10:19Why is it not fully optimized function?
10:20Because first we have written the power function 1, it has been used big of n time
10:24Here it is also big of n time
10:25I mean we are doing something wrong, we have released a special formula
10:28To half power, we are not able to optimize the time
10:32That's why we are not able to optimize because we are doing the same work
10:35What is the same work?
10:37Calculate it to the power n by 2
10:41I am using a function call here, which is my extra function call
10:45This function call is not needed
10:47Why? Because if I have removed a to the power n by 2
10:51And I store it in any variable
10:54What will happen? I have written something here
10:57Int half power is equal to power of a to the power n by 2
11:03I have removed it and stored it in this variable
11:05What can I say?
11:07Int half power square will be equal to this half power multiplied by half power
11:12What do I have learned? I have only one recursive call
11:16I have no need to call it
11:20I have no need to call it
11:20I have no need to call it
11:21What will I do?
11:21Simply store it in a variable
11:23I will store it in x
11:24And multiply it by x
11:26I can remove the term
11:28I can remove the term
11:28I will never do the recursive call
11:40I can remove the term
11:40I can remove them
11:40I have no need to call it