• 2 days ago
Transcript
00:00So now I will go back to my optimized power function, what is it in this optimized power function?
00:04I have to calculate a to the power n, so my parameters will be a and n
00:07In the base case, if n value is 0, I will return 1, because a to the power 0 is
00:12always 1
00:13Now, first of all, I have calculated half power, how do I call a to the power n by 2?
00:18Then I have taken the square of half power and square this variable
00:21Half power into half power, so this is half power square
00:26I mean, I have calculated a to the power n by 2
00:30After that, the answer has come, so I have multiplied the answer
00:33I have multiplied by the answer, my final answer which is my half power square
00:37What did I do? If I have an odd number, I have multiplied the extra a
00:43I have not multiplied by this power, so directly I have returned
00:46Now, if I have to calculate time complexity for this function, how will it be?
00:50First of all, my function call is a and n
00:55After that, who is going to call on the next level?
00:58Now, we will notice that there are not two calls in the function
01:00Only a single call is going to be
01:02Who is going to call for single call?
01:04For f and a and n by 2
01:06Then another call will be f of a and n by 4
01:10Then another call will be f of a and n by 8
01:16I will follow this function
01:16This, in this way, will be f of a and then f of a
01:22So what do I do every time?
01:24Every time, my n is divided by 2
01:27I will divide by 2
01:29I will divide by 2
01:32Every time, I will divide it by 2
01:34I worked with n
01:35Each time I divide it by 2
01:42will become two levels. How many times my recursion went? Log and base two times.
01:46This means that if I analyze my calls stack, what will happen?
01:52The first call is AN. The next call is AN by 2. The next call is AN by 4.
01:59The next call is AN by 8. So how many maximum levels in my call stack
02:07will be equal to log and base 2.
02:10So how many of my total levels will be in recursion?
02:13Or how many of my total calls will be?
02:16My total calls will always be equal to my total levels.
02:23Because here is a single level. It is the value of log in.
02:28And how many I work in one call or how many I work in one level
02:32we analyze this level.
02:34Here the work is also constant.
02:37This work is covered in my recursion.
02:40Here the work to calculate half power is constant.
02:46This work to check that it is odd or even.
02:49And then we calculate it and multiply it.
02:52This work is also constant.
02:53And the return statement is constant.
02:55This work is only non-constant.
02:56So only the non-constant work is called in recursive level.
03:01The rest of the work is in recursive function.
03:04That is a constant work.
03:05So what can I say here?
03:07All the other work per call.
03:09The work is constant k.
03:12So here the time complexity will come.
03:15Time complexity will be equal to log n into k.
03:18So I can say this will be big O of log n.
03:23This will be my total time complexity.
03:25How much space complexity will come?
03:27Space complexity will come.
03:29How many levels can become in total stack?
03:31Log n levels can become.
03:33And every time the space occupies in each level,
03:35there will be constant space occupies.
03:37Because only variables are called constant space.
03:40That's why my entire function's space complexity will be logged in.
03:43And time complexity will be logged in.
03:46I will summarize this a little bit.
03:49For last, just to write it.
03:50I have made optimized power function 3.
03:54Time complexity will come.
03:55Big O of log n.
03:57And I have seen that the power function 1 and power function 2
04:02was equal to n.
04:04So if I have to calculate power to the power n,
04:08then I will use this function in recursion.
04:13Because time complexity is equal to log n.
04:16If I compare time complexity,
04:19I can compare it in this graph.
04:21One is my power function 1 and 2.
04:23Which time complexity will be linear.
04:26One is my function.
04:28Which time complexity will be equal to log n.
04:30So what can I say?
04:32That this will always be better than this time complexity.
04:36When we talk about n or input size.
04:39So we compare that to solve any problem.
04:43Which method, which algorithm, which code is optimized,
04:46which is less optimized.
04:48So here I have released the optimized code
04:50to calculate our power function.
04:52And in this way,
04:54as many of our future chapters will be
04:56where we will study recursion more detail.
04:58We will study greedy algorithms.
04:59We will study dynamic programming.
05:01We will practice different data structures.
05:03We will study trees, graphs.
05:05When we study these things,
05:07we will always calculate time complexity
05:09and we will always know which algorithm is better.
05:14Which data structure should we use.
05:16Why the time complexity is better.
05:19Why the time complexity is better.
05:19Why the time complexity is better.
05:19Why the time complexity is better.
05:22So this is one of the most important chapters in our series.
05:25Now we introduce these things.
05:26.