For people who are confused that in odd case, it will be O(n): It is still O(log n) because in next call, n will become even. P(17) => P(16) => P(8) => P(4) => P(2) => P(1) => P(0) P(15) => P(14) => P(7) => P(6) => P(3) => P(2) => P(1) => P(0) You can actually tweak the odd case as: x^((n-1)/2) * x^((n-1)/2) * x [as (n-1)/2 + (n-1)/2 + 1 = n]. It will still be O(log n) but the number of calls would reduce a bit. It is also now evident from the looks of the expression that it will be O(log n). P(17) => P(8) => P(4) => P(2) => P(1) => P(0) P(15) => P(7) => P(3) => P(1) => P(0)
You can improve this further by doing the y calculation just before the first if statement and returning y*y inside the first else if and returning y*y*x inside the else. Here's the code in C++: double myPow(double x, int n) { if(n == 0) return 1; double y = myPow(x,n/2); if (n % 2 == 0) return y*y; else return n < 0 ? 1/x*y*y : x*y*y; } The last line accounts for the fact that n can be negative, in which case we should return 1/x*y*y.
very useful video...Now, I clearly understand about power function in program and I also written my own code in c. #include int power(int x,int n){ if(n==0) return 1; else if(n%2==0){ int y=power(x,n/2); return y*y; } else{ int y=power(x,n/2); return y*y*x; } }
In case of pinto's algorithm the odd case can be handled in this manner: x^n = x^floor(n/2) *x^floor(n/2) *x.. It that case efficiency can be highly increased if n is odd...
dude.. nice videos you make .... just arrange them in sequence... like after this there should be the calculation of time complexities but next video in the list is modular exponentiation... thanks
Java knows multiplication so essentially, you are reducing the problem to the base case scenario which is x^k where k is 0 and solving up the recursive tree using multiplication.
It is still O(log n). Please see this comment on main thread: th-cam.com/video/wAyrtLAeWvI/w-d-xo.html&lc=z13igvcwuracwzvuh23lfp4zzwnhg5135 EDIT: Copy-paste the above link in a new tab, clicking it won't work.
this one is even better int power(int x, unsigned int y) { int temp; if( y == 0) return 1; temp = power(x, y/2); if (y%2 == 0) return temp*temp; else return x*temp*temp; } int main() { printf("%d",power(2,2)); return 0; }
watching in 2020 ,after 8 years still a lot better explanation than many tutorials on youtube , (quarantine)
true dude
2021 now and it's still so relevant.
2024 still relevant
For people who are confused that in odd case, it will be O(n):
It is still O(log n) because in next call, n will become even.
P(17) => P(16) => P(8) => P(4) => P(2) => P(1) => P(0)
P(15) => P(14) => P(7) => P(6) => P(3) => P(2) => P(1) => P(0)
You can actually tweak the odd case as: x^((n-1)/2) * x^((n-1)/2) * x [as (n-1)/2 + (n-1)/2 + 1 = n]. It will still be O(log n) but the number of calls would reduce a bit. It is also now evident from the looks of the expression that it will be O(log n).
P(17) => P(8) => P(4) => P(2) => P(1) => P(0)
P(15) => P(7) => P(3) => P(1) => P(0)
where did you learn these things man?? you are a genius!!
@@shashankbangera7753 Take an analysis of algorithms course.
Now I believe the author who said when you look at recursive code for the first time it looks like black magic.
Watching it again after an year and still no one is better than you
one of the best explanations on this question so far!
Watching in 2021... and its still 1000x better than any tutorial
2024
You can improve this further by doing the y calculation just before the first if statement and returning y*y inside the first else if and returning y*y*x inside the else. Here's the code in C++:
double myPow(double x, int n) {
if(n == 0) return 1;
double y = myPow(x,n/2);
if (n % 2 == 0) return y*y;
else return n < 0 ? 1/x*y*y : x*y*y;
}
The last line accounts for the fact that n can be negative, in which case we should return 1/x*y*y.
Thank you so much. This is the best explanation I found online ☺️
The video was posted back in 2012 still better than recent videos on the same topic.
Wonderful solution!! Keep up the good work!
How does y
your explanation is so amazing thank you so much man
very useful video...Now, I clearly understand about power function in program and I also written my own code in c.
#include
int power(int x,int n){
if(n==0)
return 1;
else if(n%2==0){
int y=power(x,n/2);
return y*y;
}
else{
int y=power(x,n/2);
return y*y*x;
}
}
In case of pinto's algorithm the odd case can be handled in this manner: x^n = x^floor(n/2) *x^floor(n/2) *x.. It that case efficiency can be highly increased if n is odd...
Very well explained and very interesting! Thank you for these videos!
Thanks Anshul !
Sir how computer know that y=power(x,n/2) is actually y=x^n/2????? That is my complete confusion in this program .please.....tell me
Sir please explain
You can add one more condition, which (for n >= 1) will save you one extra function call:
*if (n == 1) return x;*
couldn't but comment.....very nice explanation ..thanks a lot
dude.. nice videos you make .... just arrange them in sequence... like after this there should be the calculation of time complexities but next video in the list is modular exponentiation... thanks
excellent explanation!
Can't thank you enough :) great vids ... keep it up
What will be complexity of pinto's code if we don't use y , just use redundant calls again ?
I got referred to this channel by my university
What about the case when x and n are not only integers but any double value?
One more optimization:
for n=odd,don't need to do x*pow(x,n-1)
instead just return y*y*x
I don't think that it will work...beacuse you need recursive call to reach base condition..
@@NikhilKumar-tk3rh
I'm sure that'll work...
Try for x^n, x=2,n=3
y=Pow(2, 3/2)
=Pow(2, 1)
=2
2^3=y*y*x
=2*2*2
=8
@@NithishKumar-se9ev just did some workout on paper...Looks like it will work 👍
anyone can share the code? I tried the exact code and it gives stack overflow error.
Show your code. I will help.
Use long long data type
What would be the Time complexity ?
this was very helpful, thanks a lot
Awesome explanation, thank you!!!
After calling the base case(x^0), how does it find (x^(n/2))?
all previous call will be pushed into callsatack and will be in pause state until its turn of execution comes..
Which software do you use?I also wish to make some competitive coding videos.
How does java know pow(x,n-1)== x^n-1??
same doubt
Java knows multiplication so essentially, you are reducing the problem to the base case scenario which is x^k where k is 0 and solving up the recursive tree using multiplication.
output = num * RecursivePower(nb, power/2) * RecursivePower(nb, power/2) // does this work for odd, if yes, why?
is Albert's algorithm an example of divide and conquer?
you are awesome man !
how it will work after removing pow function return
n is odd x^n can be written as x * x^(n-1)/2 * x^(n-1)/2
Pinto is so smart!
thanks, nice explanation !
How is Pinto's solution O(log n)?
It still O(n) in case of odd numbers. Shouldn't it be Ω(log n) since it's a lower bound.
Exactly!
It is still O(log n). Please see this comment on main thread: th-cam.com/video/wAyrtLAeWvI/w-d-xo.html&lc=z13igvcwuracwzvuh23lfp4zzwnhg5135
EDIT: Copy-paste the above link in a new tab, clicking it won't work.
Shatrughn Gupta yes I realized that shortly after commenting. Thanks :)
for the odd case, we can use x*pow(x,n/2)*pow(x,n/2) that will work better than x*pow(x,n-1).
it will work since in the odd case recursive call for n-1 is called and it becomes even then again call for n/2 resumes...
simply the best
Thank you!
Is this for java
Amazing!
for the odd case, we can use x*pow(x,n/2)*pow(x,n/2) that will work better than x*pow(x,n-1).
this channel will also help you th-cam.com/channels/oEt3glB4rWSq5zEhSGhUWA.html?view_as=subscriber
Good Explanation!!!!
nice one thanks.
Hey, this doesnt handle the case where n is negative
this one is even better
int power(int x, unsigned int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}
int main() {
printf("%d",power(2,2));
return 0;
}
Thanks for this solution man
Where can I find pinto? I wanna thank him:))
G.O.A.T
wheres the code
The one making the video is dead brother
@@vedsinha9905That's very sad. What is the name of him?
@@ksmfg4326 Harsha Suryanarayana; aka HumbleFool
Nice
Hey, your voice seems very familiar. Were you in Neso academy?
Pinto is OP
albert is now depressed.
awesomeeeeeeeeee!!!!!!!!!!!!!!!!!!!!!!!