1. 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;
}

2. What would be the Time complexity ?

3. How does y <– pow(x,n/2) work? How does he program know it needs to multiply x? If n = 8 it gets divided unless n reaches 2/2 = 1. How does the program know it needs to multiply the x's and not just add them?

4. Damn, Pinto is my firend and not me.

5. wheres the code

7. Is this for java

8. 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).

9. your explanation is so amazing thank you so much man

10. Hey, this doesnt handle the case where n is negative

11. How does java know pow(x,n-1)== x^n-1??

12. thanks, nice explanation !

13. simply the best

14. 1990 shahadat hossen shakil

couldn't but comment…..very nice explanation ..thanks a lot

15. is Albert's algorithm an example of divide and conquer?

16. 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)

17. After calling the base case(x^0), how does it find (x^(n/2))?

18. 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

19. 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.

20. You can add one more condition, which (for n >= 1) will save you one extra function call:
if (n == 1) return x;

21. Which software do you use?I also wish to make some competitive coding videos.

22. Awesome explanation, thank you!!!

23. you are awesome man !

24. Now I believe the author who said when you look at recursive code for the first time it looks like black magic.

25. Can't thank you enough 🙂 great vids … keep it up

26. Very well explained and very interesting! Thank you for these videos!

27. Thanks Anshul !